Construct the Lexicographically Largest Valid Sequence

Problem

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.

Example 1:

Input: n = 3
Output: [3,1,2,3,2]
Explanation: [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest valid sequence.

Example 2:

Input: n = 5
Output: [5,3,1,4,3,5,2,4,2]

Constraints:

1 <= n <= 20

Solution

/**
 * @param {number} n
 * @return {number[]}
 */
var constructDistancedSequence = function(n) {
    return dfs(n, Array(n), Array(n * 2 - 1), 0);
};

var dfs = function(n, used, res, m) {
    if (m >= res.length) return res;
    if (res[m]) return dfs(n, used, res, m + 1);
    for (var i = n; i > 0; i--) {
        if (used[i - 1]) continue;
        if (i !== 1 && res[m + i]) continue;
        if (m + i >= res.length && i !== 1) continue;
        used[i - 1] = 1;
        res[m] = i;
        if (i !== 1) res[m + i] = i;
        var tmp = dfs(n, used, res, m + 1);
        if (tmp) return tmp;
        used[i - 1] = 0;
        res[m] = 0;
        if (i !== 1) res[m + i] = 0;
    }
    return null;
};

Explain:

Backtrack and DFS.

Complexity:

Time complexity : O(n * n).
Space complexity : O(n).