Construct the Lexicographically Largest Valid Sequence

给一个数字n, 求[1, n]的一个序列满足除了1以外的数组出现2次, 1 出现1次. 并且要求字典序最大的数组.

这个题试了几种规律, 发现如果n是奇数, 则第二位可放n-2, 依次递减, 然后再放偶数. 但是发现这种也有漏洞. 因为1只能放一次, 所以不好判断1最后的位置, 这会影响字典序的大小, 所以最后用的广搜实现的.

class Solution {
    public int[] constructDistancedSequence(int n) {
        int[] res = new int[n * 2 - 1]; 
        boolean[] used = new boolean[n + 1];
        dfs(n, 0, res, used);
        return res;
    }
    private boolean dfs(int n, int pos, int[] res, boolean[] used) {
        if(pos == res.length) // finish placement
            return true;
        if(res[pos] != 0) // if has placed before
            return dfs(n, pos + 1, res, used);
        for(int j = n ; j >= 1; j--) {
            if(used[j])// if it is used, skip
                continue;
            if(j != 1 && j + pos >= res.length)// if it is out of bound
                continue;
            if(j != 1 && res[j + pos] != 0)// if it is used
                continue;
            res[pos] = j;
            if(j != 1)
                res[pos + j] = j;
            used[j] = true;
            if(dfs(n, pos + 1, res, used)){
                return true;
            }
            else{
                // reset
                res[pos] = 0;      
                if(j != 1)
                    res[pos + j] = 0;
                used[j] = false;
            }
            
        }
        return false;
    }
}