# 1718. Construct the Lexicographically Largest Valid Sequence
###### tags: `Leetcode` `Medium` `Backtracking`
Link: https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/description/
## 思路
backtracking
每个位置都从n到1倒序试 这样一旦找到就是lexicographically最大的
## Code

class Solution {
    public int[] constructDistancedSequence(int n) {
        int[] ans = new int[2*n-1];
        boolean[] visited = new boolean[n+1];
        backtracking(0, ans, visited, n);
        return ans;
    }
    public boolean backtracking(int index, int[] ans, boolean[] visited, int n){
        if(index==ans.length) return true;
        if(ans[index]!=0) return backtracking(index+1, ans, visited, n);
        for(int i=n; i>=1; i--){
            if(visited[i]) continue;
            visited[i] = true;
            ans[index] = i;
            if(i==1){
                if(backtracking(index+1, ans, visited, n)) return true;
            }
            else if(index+i<ans.length && ans[index+i]==0){
                ans[index+i] = i;
                if(backtracking(index+1, ans, visited, n)) return true;
                ans[index+i] = 0;
            }
            ans[index] = 0;
            visited[i] = false;
        }
        return false;
    }
}