Construct the Lexicographically Largest Valid Sequence LeetCode solution in Python

1
class Solution:
2
    def constructDistancedSequence(self, n: int) -> List[int]:
3
        self.ans = None
4

5
        def dfs(path, used, i):
6
            self.steps += 1
7
            if i == len(path):
8
                self.ans = path[:]
9
                return True
10
            if path[i] != 0:
11
                return dfs(path, used, i + 1)
12
            my_ans = [0]
13
            for x in range(n, 0, -1):
14
                if x in used:
15
                    continue
16
                if x == 1:
17
                    path[i] = x
18
                    used.add(1)
19

20
                    if dfs(path, used, i + 1):
21
                        return True
22

23
                    path[i] = 0
24
                    used.remove(1)
25
                if i + x < len(path) and path[i + x] == 0:
26
                    path[i + x] = path[i] = x
27
                    used.add(x)
28

29
                    if dfs(path, used, i + 1):
30
                        return True
31

32
                    path[i + x] = path[i] = 0
33
                    used.remove(x)
34

35
            return False
36

37
        dfs([0] * (1 + 2 * (n - 1)), set(), 0)
38

39
        return self.ans