1. 怎么看回溯题

回溯本质是 暴力搜索 + 有条件地撤销选择。它适合处理“要把所有可能方案列出来”的题,比如:

  • 从一堆数里选若干个,返回所有组合。
  • 把字符串切成若干段,要求每段满足某种条件。
  • 返回所有子集、所有排列。
  • 在棋盘上放皇后、填数独。

回溯题不要一上来就想“模板怎么背”。先把题目画成一棵搜索树:

1
2
3
4
每一层:正在做第几个选择
每条边:选择了哪个元素或切了哪一段
每个节点:当前 path 已经长什么样
叶子节点:一个完整方案,或者搜索失败

比如组合问题 n = 4, k = 2,第一层选第一个数,第二层选第二个数:

这里 [4] 不需要继续,因为后面没有数字能凑出长度为 2 的组合。这个“不继续”就是剪枝。

回溯里最常见的三个变量:

  • path:当前已经选择的内容。
  • ans:所有合法答案。
  • start_index 或 used:控制下一步可以从哪里选,避免重复或者保证顺序。

写代码时,每做一个选择就进入下一层:

1
2
3
path.append(x)
dfs(...)
path.pop()

下面用 n = 3, k = 2 跑完整个过程。重点观察:递归返回时,path 还保留着刚才的选择;程序回到上一层后执行 pop(),才真正撤销它。

append → 递归 → pop组合 n = 3, k = 2
组合问题回溯流程 逐步展示 path 添加数字、进入下一层递归、收集答案、返回上一层并弹出数字的过程。 [] [1] [2] [3] [1,2] [1,3] [2,3] 凑不够 2 个,剪枝
path
调用栈
ans
path.append(x)做选择
dfs(x + 1)进入下一层
ans.append(path[:])保存答案副本
path.pop()撤销选择

path.pop() 很重要。它表示“从当前分支退回来”,恢复到选择 x 之前的状态,然后才能尝试同一层的下一个选择。

2. 组合问题:用 start_index 保证不回头

组合问题的特点是:结果不关心顺序。[1, 2] 和 [2, 1] 是同一个组合,所以搜索时必须保证每个数字只往后选。

77. 组合 要从 1..n 中选出 k 个数。这里 start 表示这一层最小可以从哪个数字开始选:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def combine(n: int, k: int) -> list[list[int]]:
ans = []
path = []

def dfs(start: int) -> None:
if len(path) == k:
ans.append(path[:])
return

need = k - len(path)
for x in range(start, n - need + 2):
path.append(x)
dfs(x + 1)
path.pop()

dfs(1)
return ans

这段代码里最值得理解的是:

1
dfs(x + 1)

选了 x 以后,下一层只能从 x + 1 往后选。这样 [1, 2] 会出现,但 [2, 1] 不会出现。

剪枝在这里:

1
2
need = k - len(path)
for x in range(start, n - need + 2):

如果还需要 need 个数,那么当前 x 最大只能到 n - need + 1。比如 n = 4, k = 3,第一层如果选到 3,后面只剩 4 一个数,凑不够 3 个,所以没必要试。

216. 组合总和 III 是同一种思路,只是多了一个和的限制:从 1..9 里选 k 个数,和为 n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def combination_sum3(k: int, n: int) -> list[list[int]]:
ans = []
path = []

def dfs(start: int, rest: int) -> None:
if len(path) == k:
if rest == 0:
ans.append(path[:])
return

if rest < 0:
return

need = k - len(path)
for x in range(start, 10 - need + 1):
path.append(x)
dfs(x + 1, rest - x)
path.pop()

dfs(1, n)
return ans

这里 rest 表示还差多少和。每选一个 x,下一层就变成 rest - x。如果 rest < 0,说明这条路已经超了,直接返回。

组合题的复习重点是:不回头,所以用 start_index;要控制长度,就用 len(path);要控制和,就额外带一个 rest。

3. 组合总和:能不能重复选,决定下一层从哪里开始

39. 组合总和 给一组无重复正整数 candidates,每个数字可以无限次使用,返回和为 target 的所有组合。

因为一个数字可以重复使用,选了 candidates[i] 后,下一层还可以继续从 i 开始:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
candidates.sort()
ans = []
path = []

def dfs(start: int, rest: int) -> None:
if rest == 0:
ans.append(path[:])
return

for i in range(start, len(candidates)):
x = candidates[i]
if x > rest:
break

path.append(x)
dfs(i, rest - x)
path.pop()

dfs(0, target)
return ans

关键是:

1
dfs(i, rest - x)

不是 dfs(i + 1, rest - x)。因为当前数字还能继续选。

40. 组合总和 II 则相反:每个数字只能用一次,而且数组里可能有重复数字。这时下一层要从 i + 1 开始,同时同一层要跳过重复值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def combination_sum2(candidates: list[int], target: int) -> list[list[int]]:
candidates.sort()
ans = []
path = []

def dfs(start: int, rest: int) -> None:
if rest == 0:
ans.append(path[:])
return

for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue

x = candidates[i]
if x > rest:
break

path.append(x)
dfs(i + 1, rest - x)
path.pop()

dfs(0, target)
return ans

这句是回溯去重里最常见的一句:

1
2
if i > start and candidates[i] == candidates[i - 1]:
continue

它跳过的是 同一层的重复选择。比如排好序后 [1, 1, 2],第一层如果已经用第一个 1 开过一条分支,就不要再用第二个 1 开同样的分支,否则会产生重复组合。

但注意,它不是说重复数字永远不能用。如果第一个 1 已经被上一层选进 path,下一层仍然可以继续选第二个 1。所以判断里必须是 i > start,不是简单地 i > 0。

4. 切割问题:每一刀决定下一段字符串

切割问题和组合问题很像,只是选择的不是数字,而是字符串的一段。

131. 分割回文串 要把字符串切成若干段,要求每一段都是回文串。start 表示下一段从哪里开始切,end 表示这一刀切到哪里。

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
def partition(s: str) -> list[list[str]]:
ans = []
path = []

def is_palindrome(left: int, right: int) -> bool:
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True

def dfs(start: int) -> None:
if start == len(s):
ans.append(path[:])
return

for end in range(start, len(s)):
if not is_palindrome(start, end):
continue

path.append(s[start:end + 1])
dfs(end + 1)
path.pop()

dfs(0)
return ans

下面用更完整的 s = "aabaa" 演示。这个字符串既能切出单字符,也能切出 "aa"、"aba" 和 "aabaa",最后共有 6 种合法分割。

分割回文串s = "aabaa"
path
调用栈
is_palindrome(start, end)判断当前片段
path.append(piece)切下回文片段
dfs(end + 1)继续切剩余部分
path.pop()撤销这一刀
ans.append(path[:])收集完整方案
已收集方案0 / 6
还没有完整方案

切割题的终止条件通常是:

1
2
if start == len(s):
ans.append(path[:])

这表示字符串已经被完整切完。不要写成“切到某个段数就返回”,除非题目明确限制段数。

93. 复原 IP 地址 也是切割,只是每段必须是合法 IP 段,而且必须刚好切成 4 段。

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
def restore_ip_addresses(s: str) -> list[str]:
ans = []
path = []

def valid(part: str) -> bool:
if len(part) > 1 and part[0] == '0':
return False
return 0 <= int(part) <= 255

def dfs(start: int) -> None:
if len(path) == 4:
if start == len(s):
ans.append('.'.join(path))
return

remaining = len(s) - start
slots = 4 - len(path)
if remaining < slots or remaining > slots * 3:
return

for end in range(start, min(start + 3, len(s))):
part = s[start:end + 1]
if not valid(part):
continue

path.append(part)
dfs(end + 1)
path.pop()

dfs(0)
return ans

这里有两个非常实用的剪枝:

1
2
remaining < slots
remaining > slots * 3

剩余字符太少,不够每段至少 1 位;剩余字符太多,超过每段最多 3 位,都不用继续。

切割题的复习重点是:start 是下一段的起点,end 是这一刀的终点;合法才切,不合法就跳过。

5. 子集问题:每个节点都是答案

组合问题通常在 len(path) == k 时收集答案;子集问题不同,搜索树上的每个节点都是一个子集。

78. 子集 给一组无重复元素,返回所有子集:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def subsets(nums: list[int]) -> list[list[int]]:
ans = []
path = []

def dfs(start: int) -> None:
ans.append(path[:])

for i in range(start, len(nums)):
path.append(nums[i])
dfs(i + 1)
path.pop()

dfs(0)
return ans

为什么一进 dfs 就收集?

因为 path 当前是什么,就代表一个合法子集。比如 nums = [1, 2, 3]:

1
2
3
4
5
6
7
8
[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

这些都不是只在叶子节点出现,而是在搜索过程的每个节点都出现。

90. 子集 II 数组里有重复元素,返回结果不能重复。仍然是先排序,再跳过同一层重复值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def subsets_with_dup(nums: list[int]) -> list[list[int]]:
nums.sort()
ans = []
path = []

def dfs(start: int) -> None:
ans.append(path[:])

for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue

path.append(nums[i])
dfs(i + 1)
path.pop()

dfs(0)
return ans

子集题和组合题的区别很细:

  • 组合题:通常只收集满足长度或和的路径。
  • 子集题:每个 path 都是答案,所以进入递归就先收集。

6. 排列问题:用 used 控制每个位置选谁

排列问题的特点是:顺序有意义。[1, 2] 和 [2, 1] 是两个不同排列,所以不能用 start_index 控制不回头。

46. 全排列 每一层都要从所有数字里选一个还没用过的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def permute(nums: list[int]) -> list[list[int]]:
ans = []
path = []
used = [False] * len(nums)

def dfs() -> None:
if len(path) == len(nums):
ans.append(path[:])
return

for i in range(len(nums)):
if used[i]:
continue

used[i] = True
path.append(nums[i])
dfs()
path.pop()
used[i] = False

dfs()
return ans

这里的 used[i] 表示 nums[i] 是否已经在当前排列里。比如当前 path = [1, 3],那么下一层就不能再选 1 或 3,只能选还没用过的数。

47. 全排列 II 数组里有重复数字。比如 [1, 1, 2],两个 1 如果不处理,会产生重复排列。先排序,然后同一层跳过重复分支:

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
def permute_unique(nums: list[int]) -> list[list[int]]:
nums.sort()
ans = []
path = []
used = [False] * len(nums)

def dfs() -> None:
if len(path) == len(nums):
ans.append(path[:])
return

for i in range(len(nums)):
if used[i]:
continue

if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue

used[i] = True
path.append(nums[i])
dfs()
path.pop()
used[i] = False

dfs()
return ans

这句比组合去重更容易混:

1
2
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue

它的意思是:如果当前数字和前一个数字相同,并且前一个相同数字在这一层还没被用过,那当前这个重复数字就不要先开分支。

比如 [1a, 1b, 2],在同一层如果 1a 没用过,就不允许先用 1b,否则会和先用 1a 的分支重复。
但如果 1a 已经在当前路径里,比如 path = [1a],下一层当然可以用 1b,组成 [1a, 1b, 2]。

排列题的复习重点是:每一层都从头遍历数组,用 used 判断当前元素是否已经放进 path。

7. 棋盘问题:按行推进,快速判断当前位置能不能放

棋盘类回溯的特点是:每一层通常处理一行、一个格子或一个位置。判断合法时不要每次扫描整个棋盘,能用集合就用集合。

51. N 皇后 要在 n x n 棋盘上放 n 个皇后,使它们互不攻击。最自然的做法是按行放皇后:第 row 层只决定第 row 行皇后放在哪一列。

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
def solve_n_queens(n: int) -> list[list[str]]:
ans = []
board = [['.'] * n for _ in range(n)]
cols = set()
diag1 = set()
diag2 = set()

def dfs(row: int) -> None:
if row == n:
ans.append([''.join(line) for line in board])
return

for col in range(n):
if col in cols:
continue
if row - col in diag1:
continue
if row + col in diag2:
continue

board[row][col] = 'Q'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)

dfs(row + 1)

board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)

dfs(0)
return ans

为什么两条对角线可以这样表示?

1
2
同一条主对角线:row - col 相同
同一条副对角线:row + col 相同

比如 (1, 2) 和 (2, 3) 在同一条主对角线上:

1
2
1 - 2 = -1
2 - 3 = -1

所以放皇后时只要检查 cols、diag1、diag2,就能快速判断当前位置是否安全。

37. 解数独 也是棋盘回溯。它不是按行放一个,而是在空格里尝试数字。核心思路是找到一个空格,尝试填 1..9,合法就继续,不合法就撤销。

数独通常不需要返回所有解,找到一个解就可以停止。所以递归函数可以返回 True / False:

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
def solve_sudoku(board: list[list[str]]) -> None:
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
blanks = []

for r in range(9):
for c in range(9):
value = board[r][c]
box = (r // 3) * 3 + c // 3
if value == '.':
blanks.append((r, c))
else:
rows[r].add(value)
cols[c].add(value)
boxes[box].add(value)

def dfs(pos: int) -> bool:
if pos == len(blanks):
return True

r, c = blanks[pos]
box = (r // 3) * 3 + c // 3

for value in '123456789':
if value in rows[r] or value in cols[c] or value in boxes[box]:
continue

board[r][c] = value
rows[r].add(value)
cols[c].add(value)
boxes[box].add(value)

if dfs(pos + 1):
return True

board[r][c] = '.'
rows[r].remove(value)
cols[c].remove(value)
boxes[box].remove(value)

return False

dfs(0)

N 皇后是“找所有方案”,所以收集到 ans 后还要继续;数独是“找到一个解”,所以递归返回 True 时可以一路结束。

8. 去重和剪枝:先分清树层和树枝

回溯最容易混的是去重。可以用这句话区分:

1
2
树层去重:同一层不要用相同值开重复分支。
树枝去重:同一条路径上不能重复使用某个元素。

组合、子集这类“不关心顺序”的题,常见树层去重:

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

排列题既要防止同一个下标重复使用,又要防止重复值开重复分支,所以会同时用:

1
2
3
4
5
if used[i]:
continue

if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue

剪枝则是提前结束没有希望的分支:

  • 组合里剩余数字不够选,提前停。
  • 组合总和里 x > rest,后面更大,直接 break。
  • IP 地址里剩余字符太少或太多,直接返回。
  • N 皇后里列或对角线冲突,直接跳过。

回溯题写完后可以用三个问题检查:

  1. 当前 path 什么时候算答案?
  2. 下一层递归参数怎么变化?
  3. append 之后有没有对应的 pop?

9. 复习总览

  • 回溯就是在搜索树上做选择、递归、撤销选择。
  • path 记录当前路径,ans 记录所有答案。
  • 组合问题不关心顺序,用 start_index 保证不回头。
  • 组合总和能重复选时递归 dfs(i, rest - x);不能重复选时递归 dfs(i + 1, rest - x)。
  • 切割问题里 start 是下一段起点,end 是当前切割终点。
  • 子集问题每个节点都是答案,所以进入递归先 ans.append(path[:])。
  • 排列问题顺序有意义,每层都从头遍历数组,用 used 防止同一下标重复使用。
  • 有重复元素时先排序,再做同层去重。
  • 棋盘问题通常一层处理一行或一个空格,用集合加速合法性判断。
  • path.append(...) 和 path.pop() 必须成对出现;答案要存 path[:],不要直接存 path。

回溯的难点不在代码长,而在“这一层到底代表什么”。复习时先把搜索树画出来,再决定用 start_index 还是 used,最后再写递归。

avatar
LittlePyx
小P的学习、研究、生活记录
Follow Me
公告
教育经历
本科:杭州电子科技大学
研究生:电子科技大学

研究方向
AI Agent 开发、计算成像、深度学习、光学

新增:代码随想录算法刷题笔记整理中,按题型与算法模板归纳。