1. 怎么看回溯题
回溯本质是 暴力搜索 + 有条件地撤销选择。它适合处理“要把所有可能方案列出来”的题,比如:
- 从一堆数里选若干个,返回所有组合。
- 把字符串切成若干段,要求每段满足某种条件。
- 返回所有子集、所有排列。
- 在棋盘上放皇后、填数独。
回溯题不要一上来就想“模板怎么背”。先把题目画成一棵搜索树:
1 | 每一层:正在做第几个选择 |
比如组合问题 n = 4, k = 2,第一层选第一个数,第二层选第二个数:
这里 [4] 不需要继续,因为后面没有数字能凑出长度为 2 的组合。这个“不继续”就是剪枝。
回溯里最常见的三个变量:
path:当前已经选择的内容。ans:所有合法答案。start_index或used:控制下一步可以从哪里选,避免重复或者保证顺序。
写代码时,每做一个选择就进入下一层:
1 | path.append(x) |
下面用 n = 3, k = 2 跑完整个过程。重点观察:递归返回时,path 还保留着刚才的选择;程序回到上一层后执行 pop(),才真正撤销它。
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 | def combine(n: int, k: int) -> list[list[int]]: |
这段代码里最值得理解的是:
1 | dfs(x + 1) |
选了 x 以后,下一层只能从 x + 1 往后选。这样 [1, 2] 会出现,但 [2, 1] 不会出现。
剪枝在这里:
1 | need = k - len(path) |
如果还需要 need 个数,那么当前 x 最大只能到 n - need + 1。比如 n = 4, k = 3,第一层如果选到 3,后面只剩 4 一个数,凑不够 3 个,所以没必要试。
216. 组合总和 III 是同一种思路,只是多了一个和的限制:从 1..9 里选 k 个数,和为 n。
1 | def combination_sum3(k: int, n: int) -> list[list[int]]: |
这里 rest 表示还差多少和。每选一个 x,下一层就变成 rest - x。如果 rest < 0,说明这条路已经超了,直接返回。
组合题的复习重点是:不回头,所以用 start_index;要控制长度,就用 len(path);要控制和,就额外带一个 rest。
3. 组合总和:能不能重复选,决定下一层从哪里开始
39. 组合总和 给一组无重复正整数 candidates,每个数字可以无限次使用,返回和为 target 的所有组合。
因为一个数字可以重复使用,选了 candidates[i] 后,下一层还可以继续从 i 开始:
1 | def combination_sum(candidates: list[int], target: int) -> list[list[int]]: |
关键是:
1 | dfs(i, rest - x) |
不是 dfs(i + 1, rest - x)。因为当前数字还能继续选。
40. 组合总和 II 则相反:每个数字只能用一次,而且数组里可能有重复数字。这时下一层要从 i + 1 开始,同时同一层要跳过重复值:
1 | def combination_sum2(candidates: list[int], target: int) -> list[list[int]]: |
这句是回溯去重里最常见的一句:
1 | if i > start and candidates[i] == candidates[i - 1]: |
它跳过的是 同一层的重复选择。比如排好序后 [1, 1, 2],第一层如果已经用第一个 1 开过一条分支,就不要再用第二个 1 开同样的分支,否则会产生重复组合。
但注意,它不是说重复数字永远不能用。如果第一个 1 已经被上一层选进 path,下一层仍然可以继续选第二个 1。所以判断里必须是 i > start,不是简单地 i > 0。
4. 切割问题:每一刀决定下一段字符串
切割问题和组合问题很像,只是选择的不是数字,而是字符串的一段。
131. 分割回文串 要把字符串切成若干段,要求每一段都是回文串。start 表示下一段从哪里开始切,end 表示这一刀切到哪里。
1 | def partition(s: str) -> list[list[str]]: |
下面用更完整的 s = "aabaa" 演示。这个字符串既能切出单字符,也能切出 "aa"、"aba" 和 "aabaa",最后共有 6 种合法分割。
is_palindrome(start, end)判断当前片段path.append(piece)切下回文片段dfs(end + 1)继续切剩余部分path.pop()撤销这一刀ans.append(path[:])收集完整方案切割题的终止条件通常是:
1 | if start == len(s): |
这表示字符串已经被完整切完。不要写成“切到某个段数就返回”,除非题目明确限制段数。
93. 复原 IP 地址 也是切割,只是每段必须是合法 IP 段,而且必须刚好切成 4 段。
1 | def restore_ip_addresses(s: str) -> list[str]: |
这里有两个非常实用的剪枝:
1 | remaining < slots |
剩余字符太少,不够每段至少 1 位;剩余字符太多,超过每段最多 3 位,都不用继续。
切割题的复习重点是:start 是下一段的起点,end 是这一刀的终点;合法才切,不合法就跳过。
5. 子集问题:每个节点都是答案
组合问题通常在 len(path) == k 时收集答案;子集问题不同,搜索树上的每个节点都是一个子集。
78. 子集 给一组无重复元素,返回所有子集:
1 | def subsets(nums: list[int]) -> list[list[int]]: |
为什么一进 dfs 就收集?
因为 path 当前是什么,就代表一个合法子集。比如 nums = [1, 2, 3]:
1 | [] |
这些都不是只在叶子节点出现,而是在搜索过程的每个节点都出现。
90. 子集 II 数组里有重复元素,返回结果不能重复。仍然是先排序,再跳过同一层重复值:
1 | def subsets_with_dup(nums: list[int]) -> list[list[int]]: |
子集题和组合题的区别很细:
- 组合题:通常只收集满足长度或和的路径。
- 子集题:每个
path都是答案,所以进入递归就先收集。
6. 排列问题:用 used 控制每个位置选谁
排列问题的特点是:顺序有意义。[1, 2] 和 [2, 1] 是两个不同排列,所以不能用 start_index 控制不回头。
46. 全排列 每一层都要从所有数字里选一个还没用过的:
1 | def permute(nums: list[int]) -> list[list[int]]: |
这里的 used[i] 表示 nums[i] 是否已经在当前排列里。比如当前 path = [1, 3],那么下一层就不能再选 1 或 3,只能选还没用过的数。
47. 全排列 II 数组里有重复数字。比如 [1, 1, 2],两个 1 如果不处理,会产生重复排列。先排序,然后同一层跳过重复分支:
1 | def permute_unique(nums: list[int]) -> list[list[int]]: |
这句比组合去重更容易混:
1 | if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: |
它的意思是:如果当前数字和前一个数字相同,并且前一个相同数字在这一层还没被用过,那当前这个重复数字就不要先开分支。
比如 [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 | def solve_n_queens(n: int) -> list[list[str]]: |
为什么两条对角线可以这样表示?
1 | 同一条主对角线:row - col 相同 |
比如 (1, 2) 和 (2, 3) 在同一条主对角线上:
1 | 1 - 2 = -1 |
所以放皇后时只要检查 cols、diag1、diag2,就能快速判断当前位置是否安全。
37. 解数独 也是棋盘回溯。它不是按行放一个,而是在空格里尝试数字。核心思路是找到一个空格,尝试填 1..9,合法就继续,不合法就撤销。
数独通常不需要返回所有解,找到一个解就可以停止。所以递归函数可以返回 True / False:
1 | def solve_sudoku(board: list[list[str]]) -> None: |
N 皇后是“找所有方案”,所以收集到 ans 后还要继续;数独是“找到一个解”,所以递归返回 True 时可以一路结束。
8. 去重和剪枝:先分清树层和树枝
回溯最容易混的是去重。可以用这句话区分:
1 | 树层去重:同一层不要用相同值开重复分支。 |
组合、子集这类“不关心顺序”的题,常见树层去重:
1 | if i > start and nums[i] == nums[i - 1]: |
排列题既要防止同一个下标重复使用,又要防止重复值开重复分支,所以会同时用:
1 | if used[i]: |
剪枝则是提前结束没有希望的分支:
- 组合里剩余数字不够选,提前停。
- 组合总和里
x > rest,后面更大,直接break。 - IP 地址里剩余字符太少或太多,直接返回。
- N 皇后里列或对角线冲突,直接跳过。
回溯题写完后可以用三个问题检查:
- 当前
path什么时候算答案? - 下一层递归参数怎么变化?
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,最后再写递归。





