1
2
3
4
5
def dfs(root):
  if not root: return 
  for child in root.children：
    dfs(child )

1
2
3
4
5
6
7
8
9
10
11
result= []
def backtracking(路径, 选择列表):
  if(满足终止条件):
    result.append(路径)  # 收集结果
    return
    
  for 选择 in 选择列表:
    做选择
    backtracking(路径, 选择列表)
    回溯操作/撤销操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(start, path, res, n, k):
            if len(path) == k:
                res.append(path[:])
                return 

            # 添加start
            # 1、防止出现同一个原始重复使用的现象如：11 22 33 44
            # 2、防止出现 12 21这种重复出现的现象
            # [[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,1],[4,2],[4,3],[4,4]]
            # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
            for i in range(start, n+1):
                path.append(i)
                backtracking(i+1, path, res, n, k)
                path.pop()
        path, res = [], []
        backtracking(1, path, res, n, k)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(start, path, res, n, k):
            if len(path) == k:
                res.append(path[:])
                return 

            # 添加start
            # 1、防止出现同一个原始重复使用的现象如：11 22 33 44
            # 2、防止出现 12 21这种重复出现的现象
            # [[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,1],[4,2],[4,3],[4,4]]
            # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
            # 剪枝：搜索起点的上界 = n + 1 - 还需要选择的元素个数
            for i in range(start, n+1-(k-len(path))+1):
                path.append(i)
                backtracking(i+1, path, res, n, k)
                path.pop()
        path, res = [], []
        backtracking(1, path, res, n, k)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtracking(start, path, res, candidates, target):
            if target == 0:
                res.append(path[:])
                return
            # 结果 [[2,2,3],[7]]
            for i in range(start, len(candidates)):
                # 剪枝 小于0以后就不用再加进去了 之后的数肯定也是小于1的
                if candidates[i] <= target:
                    path.append(candidates[i])
                    # i: 防止出现 223 232 322重复出现
                    # i+1: 会把223给舍去
                    backtracking(i, path, res, candidates, target-candidates[i])
                    path.pop()
        path, res = [], []
        candidates.sort()
        backtracking(0, path, res, candidates, target)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # 条件：包含重复数字数组  数组中每个数字在每个组合中只能用一次  解集不能重复
        def backtracking(start, path, res, candidates, target):
            if target == 0:
                res.append(path[:])
                return  # 不需要再加进path
            for i in range(start, len(candidates)):
                # 剪枝 小于0以后就不用再加进去了 之后的数肯定也是小于1的
                if candidates[i] <= target:
                    # # 同一层 出现相同的元素 直接跳过
                    if i>start and candidates[i] == candidates[i-1]:
                        continue
                    path.append(candidates[i])
                    backtracking(i+1, path, res, candidates, target-candidates[i])
                    path.pop()
        res, path = [], []
        candidates.sort()  # 一定要排序
        backtracking(0, path, res, candidates, target)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def backtracking(start, path, res, k, n):
            if n == 0 and len(path) == k:
                res.append(path[:])
                return 
            for i in range(start, 10):
                if n > 0:
                    path.append(i)
                    backtracking(i+1, path, res, k, n-i)
                    path.pop()
        path, res = [], []
        backtracking(1, path, res, k, n)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "": return []
        keyboard = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno',
                    '7':'pqrs', '8':'tuv', '9':'wxyz'}
        def backtracking(start, path, res, digits, keyboard):
            if len(path) == len(digits):
                res.append(''.join(path[:]))
                return
            curList = keyboard[digits[start]]
            for c in curList:
                path.append(c)
                backtracking(start+1, path, res, digits, keyboard)
                path.pop()
        path, res = [], []
        backtracking(0, path, res, digits, keyboard)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def isPal(c):
            for i in range(len(c) // 2):
                if c[i] != c[~i]: return False
            return True
        def backtracking(start, path, res, s):
            if start == len(s):
                res.append(path[:])
                return
            for i in range(start, len(s)):
                # if s[start:i+1] == s[start:i+1][::-1]:
                # 判断之前截取的一段[start:i+1]是否是回文子串 
                if isPal(s[start:i+1]):
                    path.append(s[start:i+1])
                    # 上一段截取的是回文子串 开始继续截取下一段 从i+1开始
                    backtracking(i+1, path, res, s)
                    path.pop()
        res, path = [], []
        backtracking(0, path, res, s)
        return res 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        if len(s) > 12 or len(s) < 4 or len(s) == 0: return []
        def isMeeting(patch):
            # 长度不能小于1或者大于3
            if len(patch) < 1 or len(patch) > 3: return False
            # 长度大于1时不能以0开头
            if len(patch) > 1 and patch[0] == '0': return False
            # 长度等于3时不能大于255
            if len(patch) == 3:
                count = int(patch[0])*100 + int(patch[1])*10 + int(patch[2])
                if count > 255: return False
            return True
        def backtracking(start, path, res, s, depth):
            if depth == 3:
                if isMeeting(s[start:]):
                    res.append('.'.join(path + [s[start:]]))
                    return 
            for i in range(start, len(s)):
                if isMeeting(s[start:i+1]):
                    path.append(s[start:i+1])
                    backtracking(i+1, path, res, s, depth+1)
                    path.pop()
        res, path = [], []
        backtracking(0, path, res, s, 0)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtracking(start, path, res, nums):
            # 注意这里的递归出口的条件
            if start > len(nums): return 
            res.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtracking(i+1, path, res, nums)
                path.pop()
        res, path = [], []
        backtracking(0, path, res, nums)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def backtracking(start, path, res, nums):
            if start > len(nums): return
            res.append(path[:])
            for i in range(start, len(nums)):
                # 在同一层里 如果[1]选过了2->[1,2] 那么下一次[1]再碰到2就直接跳过
                if i > start and nums[i] == nums[i-1]:
                    continue
                path.append(nums[i])
                backtracking(i+1, path, res, nums)
                path.pop()
        path, res = [], []
        nums.sort()
        backtracking(0, path, res, nums)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        # 1、长度至少为2 
        # 2、必须递增(可以相等)
        # 3、不重复
        def backtracking(start, path, res, nums):
            # 长度至少为2
            if len(path) >= 2: 
                res.append(path[:])
                # 注意这里没有return 因为当前path找到一个还需要继续往下找
            # 在不能sort的情况下排除当前层的重复结果一般是使用一个used数组
            used = []
            for i in range(start, len(nums)):
                # 保证递增  保证不重复(判断当前层有没有用过nums[i])
                if (len(path)>0 and path[-1] > nums[i]) or nums[i] in used:
                    continue
                path.append(nums[i])
                used.append(nums[i])
                backtracking(i+1, path, res, nums)
                path.pop()
        res, path = [], []
        backtracking(0, path, res, nums)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # 数字不重复的数组 全排列 答案不能相同  
        def backtracking(path, res, nums, used):
            if len(path) == len(nums): 
                res.append(path[:])
                return 
            for i in range(len(nums)):
                if used[i] == 1: continue  # 每个元素只能用一次
                path.append(nums[i])
                used[i] = 1
                backtracking(path, res, nums, used)
                used[i] = 0
                path.pop()
        path, res = [], []
        used = [0] * len(nums)
        backtracking(path, res, nums, used)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # 可重复数组 全排列 不重复
        def backtracking(path, res, nums, used):
            if len(path) == len(nums): 
                res.append(path[:])
                return
            for i in range(len(nums)):
                if used[i] == 1: continue
                # 减去重复的结果 
                # i>0 进入该层>=2个数 如果当前层和前面层相同 且前面层访问过了 剪掉 ？？？
                if i>0 and nums[i]==nums[i-1] and not used[i-1]: continue
                path.append(nums[i])
                used[i] = 1
                backtracking(path, res, nums, used) # 进入下一层
                used[i] = 0
                path.pop()
        path, res = [], []
        used = [0] * len(nums)
        nums.sort()
        backtracking(path, res, nums, used)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # 同一行 board[1][0] [1][1] [1][2] [1][3] [1][4]
        # 同一列 board[0][1] [1][1] [2][1] [3][1] [4][1]
        # 斜行   board[1][0] [2][1] [3][2] [4][3] 差值相同
        #        board[1][3] [2][2] [3][1] 和值相同
        # 这种方法时间复杂度较高
        def check(board, row, col):
            for i in range(n):
                if board[row][i] == 'Q' or board[i][col] == 'Q': return False
            for i in range(n):
                for j in range(n):
                    if ((i+j) == (row+col) and board[i][j] == 'Q') or ((i-j) == (row-col) and board[i][j] == 'Q'): return False
            return True
        def backtracking(res, board, row):
            if row == n:
                res.append([''.join(row) for row in board])
                return
            for i in range(n):
                if check(board, row, i) == True:
                    board[row][i] = 'Q'
                    backtracking(res, board, row+1)
                    board[row][i] = '.'
        board = [['.']*n for i in range(n)]
        res = []
        backtracking(res, board, 0)
        return res

1
2

1
2