30 秒识别Q1 · 77 Combinations：从 1..n 中选出所有长度为 k 的组合。你的第一反应是哪个模式？
看答案
回溯（模板 A）。「所有组合」= 枚举方案本身。剪枝点：当剩下的数不够凑满 k 个时直接返回，range(start, n - (k - len(path)) + 2)。
「撤销选择」是它和普通 DFS 的唯一区别，也是它叫回溯的原因：同一个 path 数组被所有分支共用，走完一条路必须恢复原状，否则兄弟分支拿到的是脏数据。记答案时一定 path[:] 拷贝，同理。
识别它很容易：题面里有「所有」「列出全部方案」「有多少种走法并要求给出方案」，而且数据规模小得反常（n ≤ 20）——因为答案数量本身就是指数级的，出题人不会给你大数据。
| 题面出现… | 想到 |
|---|---|
| 「所有子集 / 所有组合 / 所有排列」 | 模板 A（组合）或模板 B（排列） |
| 「列出全部方案 / 打印所有路径」 | 回溯，答案是方案本身而不是个数 |
| 「在矩阵里找一个单词 / 一条路径」 | 网格回溯：标记 → 递归 → 还原 |
| 「把字符串切成若干段，每段都要满足…」 | 切割型回溯，切点就是选择 |
| n ≤ 20 却要枚举，或明确说「保证答案不超过 X 个」 | 指数级枚举被默许了 |
| 「棋盘 / 皇后 / 数独」 | 回溯 + 冲突集合剪枝 |
题目只要方案数、不要方案本身，几乎一定是 DP（第 16、17 章）——回溯枚举完再数一遍是指数级，DP 是多项式级。只要最优值（最大 / 最小）同理，先想 DP 或贪心（第 15 章）。网格上数连通块（第 10 章）用的是 DFS 但不撤销：格子一旦访问就永久标记，因为你不需要「换一条路再走一遍」。看到「还原现场」这个动作才是回溯。最后一个同名陷阱：「排列」这个词在第 03 章 567 也出现，但那道题问的是「s1 的某个排列是否作为子串出现」——比对字符计数即可，真去枚举排列就爆了。要不要真的列出方案，永远是第一道分水岭。
■ 【骨架】 不变，闭着眼默写 ■ 【插槽】 随题变化，写题前先问自己填什么
def subsets(nums):
res, path = [], [] # 【骨架】path = 当前走到哪
def dfs(start): # 【插槽】start 表示"不许回头",排列题换成 used
res.append(path[:]) # 【插槽】何时记答案:每个节点 / 只在叶子;必须拷贝
for i in range(start, len(nums)): # 【骨架】枚举本层的选择
path.append(nums[i]) # 【骨架】做选择
dfs(i + 1) # 【插槽】i+1 = 每个数最多用一次;i = 可重复用
path.pop() # 【骨架】撤销选择
dfs(0)
return resdfs(i + 1) 每个数用一次，dfs(i) 可以重复用——一个字符的差别就是 78 和 39 的差别。def permutations(nums):
res, path = [], []
used = [False] * len(nums) # 【骨架】排列没有"不许回头",靠 used 防重复取
def dfs():
if len(path) == len(nums): # 【插槽】终止条件 = 叶子的定义
res.append(path[:]) # 【骨架】记答案要拷贝
return
for i, x in enumerate(nums): # 【骨架】每层都从头枚举
if used[i]: # 【骨架】
continue
used[i] = True # 【骨架】做选择
path.append(x)
dfs() # 【骨架】
path.pop() # 【骨架】撤销选择
used[i] = False
dfs()
return resstart），排列「每层都从头选」（used）。网格题（79）本质是排列型——board[i][j] = '#' 就是它的 used。i 而不是 i + 1（同一个数可重复用）。排序后 if candidates[i] > remain: break 是本章性价比最高的剪枝。if i > start and nums[i] == nums[i-1]: continue。条件是 i > start 不是 i > 0，见翻车点②——这是全章最常写错的一行。'#' 表示占用，递归结束后必须还原；不还原就变成了第 10 章的洪水填充，答案会漏。r - c、副对角线 r + c。说得出这三个集合就够。res.append(path) 存的是同一个列表对象的引用，回溯完它会被改空。必须 path[:] 或 list(path)。这是本章 90% 的「答案全是空数组」的原因。i > 0——if i > start and nums[i] == nums[i-1] 里的 start 不能换成 0。写成 i > 0 会把 [1,2,2] 里合法的 [1,2,2] 也剪掉——同一层的重复才要跳过，父子关系上的重复是合法的。path.append + used[i] = True）就要撤两件事。网格题里 board[i][j] = '#' 之后忘了还原，会让后续搜索少掉大片可用格子。break（39）、剩余元素不够就返回（77）、冲突集合（51）——面试里主动讲剪枝比写完更重要。30 秒识别Q1 · 77 Combinations：从 1..n 中选出所有长度为 k 的组合。你的第一反应是哪个模式？
回溯（模板 A）。「所有组合」= 枚举方案本身。剪枝点：当剩下的数不够凑满 k 个时直接返回，range(start, n - (k - len(path)) + 2)。
30 秒识别Q2 · 17 Letter Combinations of a Phone Number：给一串电话数字，返回它能表示的所有字母组合。你的第一反应是哪个模式？
回溯。每一位数字对应一层，本层的选择列表就是这个数字映射的几个字母。「所有组合」+ 输入长度很短（≤ 4），指数级枚举被默许。
30 秒识别Q3 · 377 Combination Sum IV：给一个无重复正整数数组和目标值，求总和为目标值的组合个数（顺序不同算不同）。你的第一反应是哪个模式？
一维 DP，不是本章——名字里带 Combination，要的却只是个数。回溯枚举完再数是指数级；dp[t] = Σ dp[t - num] 是 O(n·target)。见 §2 分流条件：要方案本身才回溯，要个数就 DP。
每章自测都会混入恰好一道非本章题，防止「读哪章选哪章」的条件反射；题面也一律取自本章未收录的题，避免凭记忆而非凭信号作答。