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.

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:

class Solution {
    Set<Integer> visited;
    
    public int[] constructDistancedSequence(int n) {
        int[] res = new int[2 * n - 1];
        if (n == 1) {
            res[0] = 1;
            return res;
        }
        res[0] = res[n] = n;
        int state = 1 << n;
        visited = new HashSet();
        dfs(res, state, n);
        return res;
    }
    
    private boolean dfs(int[] res, int state, int n) {
        // System.out.println(Arrays.toString(res) + Integer.toBinaryString(state));
        if (state == (1 << (n + 1)) - 2) return true;
        if (!visited.add(Arrays.hashCode(res))) return false;
        for (int i = 0; i < res.length; i ++) {
            if (res[i] != 0) continue;
            for (int j = n - 1; j > 1; j --) {
                if (((1 << j ) & state) == 0 && i + j < 2 * n - 1 && res[i + j] == 0) {
                    res[i] = res[i + j] = j;
                    if (dfs(res, state | (1 << j), n)) {
                        return true;
                    }
                    res[i] = res[i + j] = 0;
                }
            }
            if (((1 << 1) & state) > 0) return false;
            res[i] = 1;
            if (dfs(res, state | (1 << 1), n)) {
                return true;
            }
            res[i] = 0;
        }
        return false;
    }
}