1718: Construct-the-Lexicographically-Largest-Valid-Sequence
Medium

The constraints are practically asking for brute-force. You do not need to find any special tricks; there is no way you TLE.

Since, we are trying to find the lexicographically largest answer, realise that for each index, if we start checking every value from n to 1, the first answer we return will naturally be the lexicographically largest answer.

Code:

class Solution {
private:
    bool recursion (int index, int n, vector<int>& current, vector<int>& used) {
        if (index == current.size()) {
            return true;
        }
        if (current[index] != 0) {
            return recursion(index+1, n, current, used);
        }
        for (int i = n; i >= 1; --i) {
            if (used[i] == 1) continue;

            current[index] = i;
            used[i] = 1;

            if (i == 1) {
                if (recursion(index+1, n, current, used)) {
                    return true;
                }
            } else if (index+i < 2*n-1 && current[index+i] == 0) {
                current[index+i] = i;

                if (recursion(index+1, n, current, used)) {
                    return true;
                }
                
                current[index+i] = 0;
            }

            current[index] = 0;
            used[i] = 0;
        }
        return false;
    }
public:
    vector<int> constructDistancedSequence(int n) {
        vector<int> current (2*n-1, 0);
        vector<int> used (n+1, 0);

        recursion(0, n, current, used);
        return current;
    }
};

Complexity:

Learnings:

Time taken: