Description

Submission

class Solution {
    int size;
    int n;
    bool found;
    vector<int> rets;
    vector<int> ret;
    vector<int> numTaken;
    
    void disp(vector<int>& v) {
        for(auto x: v) {
            cout << x << " ";
        }
        cout << endl;
    }
    
    void backtrack(int pos, int left) {
        if(found) return;
        if(left == 0) {
            found = true;
            ret = rets;
            return;
        }
        
        if(rets[pos]) {
            backtrack(pos+1, left);
            return;
        }
        
        for(int i = n; i >= 1; --i) {
            if(numTaken[i]) continue;
            if(i == 1) {
                rets[pos] = 1;
            } else {
                if(i + pos >= size || rets[i+pos]) continue;
                rets[pos] = rets[i+pos] = i;
            }
            numTaken[i] = 1;

            backtrack(pos+1, left-1);
            if(i == 1) {
                rets[pos] = 0;
            } else {
                rets[pos] = rets[i+pos] = 0;
            }
            numTaken[i] = 0;
        }
    }
public:
    vector<int> constructDistancedSequence(int n) {
        size = 2 * n - 1;
        this->n = n;
        found = false;
        rets.resize(size, 0);
        numTaken.resize(n+1, 0);
        backtrack(0, n);
        return ret;
    }
};