Backtrack

1
result = []
2
def backtrack(path, choices):
3
    if satisfies end condition:
4
        result.add(path)
5
        return
6

7
    for choice in choices:
8
        make the choice
9
        backtrack(path, choices)
10
        withdraw the choice

1
def permute(nums: list[int]) -> list[list[int]]:
2
    ans = []
3
    track = []
4
    used = [False] * len(nums)
5

6
    def backtrack(nums, track, used):
7
        if len(track) == len(nums):
8
            ans.append(track.copy())
9
        for i, num in enumerate(nums):
10
            if used[i]:
11
                continue
12
            track.append(num)
13
            used[i] = True
14
            backtrack(nums, track, used)
15
            track.pop()
16
            used[i] = False
17

18
    backtrack(nums, track, used)
19
    return ans

Generate Parentheses

Some pruning conditions:

left and right represent the number of parentheses that can still be used. If at some point left is greater than right, it means there are more ) than ( in the track, which is invalid.
If at any point left or right is less than 0, it means we have used more parentheses than allowed, which is invalid.

Solution:

1
def generateParenthesis(n: int) -> list[str]:
2

3
    def backtrack(track: str, left: int, right: int):
4
        if left == 0 and right == 0:
5
            ans.append(track[:])
6
        if left > right:
7
            return
8
        if left < 0 or right < 0:
9
            return
10

11
        track += "("
12
        backtrack(track, left-1, right)
13
        track = track[:-1]
14

15
        track += ")"
16
        backtrack(track, left, right-1)
17
        track = track[:-1]
18

19
    ans = []
20
    backtrack("", n, n)
21
    return ans

Numbers With Same Consecutive Differences

Leetcode

Solution:

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

5
        def backtrack(track: int, num_digit: int):
6
            if num_digit == n:
7
                ans.append(track)
8
                return
9

10
            for i in range(10):
11
                if track == 0 and i == 0:
12
                    continue
13
                if track > 0 and abs((track % 10) - i) != k:
14
                    continue
15
                track = track * 10 + i
16
                num_digit += 1
17
                backtrack(track, num_digit)
18
                track = (track - track % 10) // 10
19
                num_digit -= 1
20

21
        backtrack(0, 0)
22
        return ans