1718.-construct-the-lexicographically-largest-valid-sequence.md

1718. Construct the Lexicographically Largest Valid Sequence

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        
        
        self.path = [0] * (n * 2 - 1)
        used = [0] * (n + 1)
        self.dfs(0, n, used)
        return self.path 
    
    def dfs(self, idx, n, used):
    
        if idx == (n * 2 - 1) : return True
        
        if self.path[idx] : return self.dfs(idx + 1, n, used)
        
        ## 倒叙字典序最大
        for i in range(n , 1, - 1):
            if not used[i] and idx + i < 2 * n - 1 and not self.path[idx + i] :
                self.path[idx] = self.path[idx + i] = i
                used[i] = 1
                if self.dfs(idx + 1, n , used) : return True
                used[i] = 0
                self.path[idx] = self.path[idx + i] = 0
                
        if not used[1]:
            used[1] = 1
            self.path[idx] = 1
            if self.dfs(idx + 1, n , used) : return True
            self.path[idx] = 0
            used[1]=0
            
        return False