回溯模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

其中，关于循环体，由于限制的不同，循环的方式也不同。

• 1每次循环都从0开始，每一次重复搜索

for i in range(idx,n):
	dfs(idx)
1
2

• 2每次循环都从i开始，也就是最外层循环一次，内层每一层起始点从i开始

for i in range(idx,n):
	dfs(i)
1
2

• 3每次循环都从i+1开始 .不重复检索，每一层起始点都+1

for i in range(idx,n):
	dfs(i+1)
1
2

题目总览

组合问题

第77题. 组合

题目：
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

思路：

回溯第一题。

横向在大区间取数，纵向在小区间取数。用递归控制for循环的嵌套数量。

代码：

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        def backtracking(idx,path):
            if len(path) == k:  # 终止条件，注意没有return，需要全局遍历。
                res.append(path[:])
            for i in range(idx,n):   # for循环控制横向遍历
                path.append(i+1)
                backtracking(i+1,path)  # 递归进入小区间，控制纵向遍历
                path.pop()  # 回溯过程
        backtracking(0,[])
        return res
1
2
3
4
5
6
7
8
9
10
11
12

216. 组合总和 III

题目：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

思路：
和上题 变化了终止条件，增加了path总和，在path个数基础上。所以修改终止条件即可。

代码：

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        def backtracing(idx, path):
            if sum(path) == n and len(path) == k:
                res.append(path[:])
            elif sum(path) > n or len(path) > k:  # 剪枝
                return
            for i in range(idx,10):
                path.append(i)
                backtracing(i+1, path)  # 不重复选取，从i+1开始
                path.pop()
        backtracing(1,[])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

39. 组合总和

题目：
不重复数据，和为target的组合，每个数字可以重复选取

思路：
与上题相比，多了一个可重复选取的条件，即对应idx的遍历顺序，需要从i+1,变为i开始。这样保证每次一次递归还是从自己开始，可以重复选取。

class Solution:
    def combinationSum(self, candidates: List[int], target: int):
        res = []
        def backtracing(idx,path,s):
            if idx > len(candidates)-1 or sum(path[:]) > s:
                return   # 终止条件
            if sum(path) == s:
                res.append(path[:])
            for i in range(idx,len(candidates)):
                path.append(candidates[i])
                backtracing(i,path,s)  # 可以重复选取，从i开始，对比上题。
                path.pop()
        backtracing(0,[],target)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

40.组合总和II

题目：

含重复元素的candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。每个编号最多使用一次。

---

思路：
与上题相比，没有可重复选数的限制，元素是可重复的。
由于计算组合中，先后顺序不影响结果，也就是要求：

• 横向不处理重复元素
• 纵向要处理重复元素

所以在于去重。横向和纵向的最大区别在于，i和idx的关于。横向的i一定大于idx，因为重复数字一定在第2位之后。

而在纵向中，每个重复数字都是第1位

所以通过 if i> idx and c[i]==c[i-1] 来判断是横向的重复数字，然后continue即可。

千万不可以return，这样横向到这个数字就截止了。后面自然也没有了。

---

代码：

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        print(candidates)
        def backtracing(idx,path):
            if sum(path) > target:
                return
            if sum(path) == target:
                res.append(path[:])
            for i in range(idx,len(candidates)):
                if candidates[i] == candidates[i-1] and i > idx:
                    continue   # 关键的去重步骤
                path.append(candidates[i])
                backtracing(i+1,path)
                path.pop()
        backtracing(0,[])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

17.电话号码的字母组合

题目：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

---

思路：

这里的idx是用来标记第几层数字的，而不是某层的第几个字母的。所以思路与之前不一样。

---

代码：

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        d = {'2':'abc',
             '3':'def',
             '4':'ghi',
             '5':'jkl',
             '6':'mno',
             '7':'pqrs',
             '8':'tuv',
             '9':'wxyz',
             }
        k = len(digits)
        res = []
        if not digits:return []
        def backtracing(idx,path):
            if len(path) == k:
                res.append(''.join(path[:]))
                return
            s = d[digits[idx]]
            for i in s:
                path.append(i)
                backtracing(idx+1,path)
                path.pop()
        backtracing(0,[])
        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

排列问题

46.全排列

题目：
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

---

思路：
排列和组合的区别在于纵向循环是从头开始的。

---

代码

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        def backtracing(idx,path):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(idx,len(nums)):
                if nums[i] in path:
                    continue
                backtracing(0,path+[nums[i]])
        backtracing(0,[])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13

47.全排列 II

题目：
与上题相比，区别在于本题的数字可以重复。

---

思路：
对应着,去重需要分别在树层之间和树枝间进行。
树枝间去重，和上题一样。但本次引入used数组进行标记，最已使用的树枝不在遍历。

树层间去重，类似组合40题，判断相邻两个是否相等。

---

代码：

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        t = [False] * len(nums)
        nums.sort()
        def backtracing(idx,path):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                # 同一树层的重复值，跳过
                if i > idx and nums[i] == nums[i-1] and t[i-1] == False:
                    continue
                # 同一树枝的重复值，跳过
                if not t[i]: 
                    t[i] = True
                    backtracing(0,path+[nums[i]])
                    t[i] = False
        backtracing(0,[])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

分割问题

131. 分割回文串

题目：
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

---

思路：

和组合问题类似，当时也有不同，组合问题是从nums里面逐个去数字，所以idx逐个+1即可。但是本题的分割问题，需要起止点两个索引.

path.append的值也发生变化：s[idx,i+1]

终止条件，也根据idx的位置进行：if idx == len(s): res.append(path[:]) return

---

代码

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def huiwen(s):
            return s == s[::-1]
        res = []
        def backtracing(idx, path):
            if idx == len(s):
                res.append(path[:])
                return
            for i in range(idx,len(s)):
                a = s[idx:i+1]
                if huiwen(a):
                    path.append(a)
                    backtracing(i+1,path)
                    path.pop()
                # 不可以else:return,比如ef不是回文，efe是回文
                # 一旦return，遇到一个非回文ef就终止后后面的分隔efe
                # else:  
                #     return
        backtracing(0,[])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

93. 复原 IP 地址

题目：
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

---

思路：
将上文的回文串限制改为了ip限制，对数字的大小进行约束，以及path的长度。

---

代码：

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def isIp(x):
            if len(x) > 1 and x[0] == '0':
                return False
            if int(x) > 255 or int(x) < 0:
                return False
            return True
        res = []
        def backtracing(idx,path):
            if len(path) > 4:
                return
            if idx == len(s) and len(path)== 4:
                res.append(path[:])
                return
            for i in range(idx,len(s)):
                a = s[idx:i+1]
                if isIp(a):
                    path.append(a)
                    backtracing(i+1,path)
                    path.pop()
        backtracing(0,[])
        return ['.'.join(i) for i in res]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

子集问题

78.子集

题目：
不重复数组的所有子集

---

思路：
本题要求取出所有节点，而不是之前的叶子节点。

---

代码

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        def backtracing(idx,path):
            res.append(path[:])  # 取出所有节点
            for i in range(idx,len(nums)):
                path.append(nums[i])
                backtracing(i+1,path)
                path.pop()
        backtracing(0,[])
        return res
1
2
3
4
5
6
7
8
9
10
11

90.子集II

题目：
对于重复值的子集

---

思路
加上树层去重即可

if i > idx and nums[i] == nums[i-1]:
	continue
1
2

---

代码

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        def backtracing(idx,path):
            res.append(path[:])
            for i in range(idx,len(nums)):
                if i > idx and nums[i] == nums[i-1]:
                    continue
                path.append(nums[i])
                backtracing(i+1,path)
                path.pop()
        backtracing(0,[])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

棋盘问题

51. N 皇后

题目：
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

---

思路：
是一个二维的回溯问题，看作是全排列问题，当时需要针对性的条件进行剪枝。也就是规则/

难点1：二维数组如何表示

• chessboard = [[‘.’ for _ in range(n)] for _ in range(n)]

难点2：如果判断是否有效

• 行（不用判断，因为每行必然只有一个。
• 列：需要判断。
• 45度斜线：右上角即可，因为本行以下未生成。
• 135度斜线：需要判断左上角即可。）

难点3：如何回溯

• chessboard[idx][j] = ‘Q’
  backtracing(idx+1,chessboard,n)
  chessboard[idx][j] = ‘.’

难点4：二维数组的拷贝（深拷贝）
由于二维数组是可变元素，里面每个元素也是可变元素，所以在保存res的时候，直接保存或者浅拷贝会出现无法拷贝的情况。所以需要深拷贝

看这篇文章

或者将二维变成一维，在进行保存到res。

---

代码

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
		# 1 生成二维数组，初始化均为'.'
        chessboard = [['.' for _ in range(n)] for _ in range(n)] 
        # 判断落点是否有效。
        def is_valid(row, col, chessboard):
            for j in range(n):  # 列检查
                if chessboard[j][col] == 'Q':
                    return False
            # 左上角检查
            i = row - 1
            j = col - 1
            while i >=0 and j >= 0:
                if chessboard[i][j] == 'Q':
                    return False
                i -= 1
                j -= 1
            # 右上角检查：
            i = row - 1
            j = col + 1
            while i >= 0 and j < n:
                if chessboard[i][j] == 'Q':
                    return False
                i -= 1
                j += 1
            return True

        def backtracing(idx,chessboard,n):
            if idx == n:
                print(chessboard)
                ress = []
                # 二维数组变成一维
                for i in chessboard:
                    ress.append(''.join(i))
                res.append(ress)
            for j in range(n):
            	# 有效进行处理，无效继续向右走，在for循环里面。
                if is_valid(idx, j, chessboard):  
                    chessboard[idx][j] = 'Q'
                    backtracing(idx+1,chessboard,n)
                    chessboard[idx][j] = '.'
        backtracing(0,chessboard,n)
        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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44