1718. Construct the Lexicographically Largest Valid Sequence

Given an integer n, find a sequence that satisfies all of the following:

• The integer 1 occurs once in the sequence.
• Each integer between 2 and n occurs twice in the sequence.
• For every integer i between 2 and n, the distance between the two occurrences of i is exactly
  i.

The distance between two numbers on the sequence, a[i] and a[j], is the absolute difference of their indices, |j - i|.

Return the lexicographically largest sequence. It is guaranteed that under the given constraints, there is always a solution.

A sequence a is lexicographically larger than a sequence b (of the same length) if in the first position where a and b differ, sequence a has a number greater than the corresponding number in b. For example, [0,1,9,0] is lexicographically larger than [0,1,5,6] because the first position they differ is at the third number, and 9 is greater than 5.

class Solution {
    bool helper(vector<int>& res, int p, int mask, int n) {
        if(p == res.size()) return true;
        else {
            if(res[p] != -1) return helper(res, p + 1, mask, n);
            for(int i = n; i >= 1; i--) {
                if(mask & (1<<i)) continue;
                if(i == 1) {
                    res[p] = 1;
                    if(helper(res, p + 1, mask | (1<<i),n)) return true;
                    res[p] = -1;
                } else {
                    if(p + i >= res.size() or res[p+i] != -1) continue;
                    res[p+i] = res[p] = i;
                    if(helper(res, p + 1, mask | (1<<i),n)) return true;                
                    res[p+i] = res[p] = -1;
                }
            }
            return false;
        }
    }
public:
    vector<int> constructDistancedSequence(int n) {
        vector<int> res(n * 2 - 1,-1);
        helper(res,0,0,n);
        return res;
    }
};