1718. Construct the Lexicographically Largest Valid Sequence (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        def dfs(path, k):
            if len(path) < n:
                i = self.result.index(0)
                for num in range(k, 0, -1):
                    if num not in self.result:
                        if num > 1:
                            if i + num < m and self.result[i + num] == 0:
                                self.result[i] = self.result[i + num] = num
                                dfs(path + [i], n)
                                break
                        else:
                            self.result[i] = num
                            dfs(path + [i], n)
                            break
                else:
                    num = self.result[path[-1]]
                    self.result[path[-1]] = 0
                    if num > 1:
                        self.result[path[-1] + num] = 0
                    dfs(path[ : -1], num - 1)
        m = 2 * n - 1
        self.result = [0] * m
        dfs([], n)
        return self.result