Construct the Lexicographically Largest Valid Sequence LeetCode solution in C++

1
class Solution {
2
 public:
3
  int SIZE, N;
4

5
  bool fillIndex(vector<int> &a, vector<bool> &used, int idx) {
6
    if (idx == SIZE) return true;
7
    if (a[idx]) return fillIndex(a, used, idx + 1);
8

9
    for (int num = N - 1; num >= 1; num--) {
10
      if (used[num]) continue;
11
      if (num != 1 and (idx + num >= SIZE or a[idx + num] != 0)) continue;
12
      a[idx] = num;
13
      if (num != 1) a[idx + num] = num;
14
      used[num] = true;
15
      if (fillIndex(a, used, idx + 1)) return true;
16
      a[idx] = 0;
17
      if (num != 1) a[idx + num] = 0;
18
      used[num] = false;
19
    }
20

21
    return false;
22
  }
23

24
  vector<int> constructDistancedSequence(int n) {
25
    SIZE = 1 + (n - 1) * 2, N = n;
26
    vector<int> a(SIZE, 0);
27
    vector<bool> used(n, false);
28

29
    if (n == 1) {
30
      a[0] = 1;
31
    } else {
32
      a[0] = a[n] = n;
33
      used[n] = true;
34
      fillIndex(a, used, 1);
35
    }
36

37
    return a;
38
  }
39
};