我最近集中刷完了一批回溯相关的 LeetCode 题目从找出所有子集的异或总和再求和到全排列 II再到电话号码字母组合括号生成组合目标和组合总和字母大小写全排列刷完之后最大的感受是网上讲回溯的文章很多但大多数把回溯讲得跟玄学一样——递归栈、状态恢复、剪枝条件、横向纵向去重一套组合拳下来新手直接懵。这个专题我可以负责任地说回溯没有那么多花样它本质上就是在一棵决策树上做深度优先遍历。你把树画出来代码其实就是那三行模板的变体。所谓排列、组合、子集、字符串生成、括号匹配全是在同一个模板上换每层选什么和选了之后下一步从哪儿开始而已。这篇文章我会把这 8 道题的核心解法、代码模板、去重逻辑、剪枝时机全部串起来讲重点解释为什么这样写而不是只贴答案。尤其会讲清楚三个最容易被卡住的问题startIndex到底怎么用、used数组去重的两种写法有什么区别、以及看上去和排列组合完全不沾边的题比如括号生成、目标和是怎么变成回溯题的。如果你是正在准备算法面试或者刚学到递归搜索这一章觉得似懂非懂这篇文章应该能帮你把这几类题一次性理清楚。1. 先把回溯这个东西看透一棵决策树 三行模板1.1 为什么所有回溯题都是同一棵树回溯算法解决的核心问题是在多个选择面前穷举所有可能路径。我说的穷举不是暴力 for 循环那种穷举而是一种带状态的分步穷举。想象你在一个岔路口面前有三条路你选了第一条走进去发现前面又是岔路口又得选一条就这样一层层走下去直到走不动为止。走到头之后你退回到上一个岔路口换另一条路继续走。这个走进去再退出来的过程就是回溯backtracking。递归天然支持这种进入下一层再返回上一层的行为所以回溯总是和递归一起出现。你把这 8 道题全部套进这个模型里看一下子集异或总和每个元素选 or 不选二叉决策树。全排列 II每层从剩余元素中选择一个排到当前位置多叉决策树。电话号码字母组合第一个数字对应的字母中选一个第二个数字对应的字母中选一个每层选择集合不同多叉树。括号生成每层选择放左括号还是右括号二叉决策树。组合从 n 个数中选 k 个数每层决定当前位置放哪个数多叉树。目标和每个数前面放正号还是负号二叉决策树。组合总和每个位置从候选数中选一个允许重复选多叉树。字母大小写全排列每个字母选择大写还是小写二叉决策树。所以你看题目千变万化底层都是同一棵树。你只要学会把问题抽象成树的每一层代表一个决策节点每个分支代表一种选择代码就是顺水推舟的事。1.2 那个让你背下来的三行模板到底在干嘛回溯代码流传最广的模板大概是这样的def backtrack(路径, 选择列表): if 满足结束条件: 结果.append(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择很多人背下来了但不知道为什么。我拆给你看backtrack(路径, 选择列表)走到当前节点时已经做出的选择记录在路径里接下来还能做什么选择记录在选择列表里。这个函数的功能是在当前状态下尝试所有可能的选择并继续往下走。if 满足结束条件走到树的叶子节点或者满足题目要求的目标状态时把当前路径保存下来不再往下走。for 选择 in 选择列表当前层所有可选的分支一个分支一个分支地尝试。做选择把当前选择追加到路径里同时更新选择列表。backtrack带着新状态进入下一层。撤销选择回到当前层时把刚才的选择从路径里删掉恢复现场准备尝试下一个分支。这里最关键的一步是撤销选择。因为选择列表和路径在很多实现里是共用的可变对象比如同一个列表你不撤销上次的选择下一个分支就会带着脏数据往下走。这就是老手常说的恢复现场。提示如果你不想手动撤销可以每次递归时传一个新构造的列表比如path [num]但这会产生大量临时对象数据量大的时候内存和耗时都会明显上升。刷题阶段无所谓但理解撤销才能写出高效写法。1.3 path、used、startIndex 三个变量的真实含义这三个变量是回溯题的灵魂三件套很多题就是围绕它们做文章path当前路径即已经做出的选择序列。比如全排列中已经排好的前几个位置。used记录某个元素是否已经被使用。只有排列类问题需要它因为排列看顺序第 i 层和第 j 层可能用到同一个元素但一个元素不能同时出现在两个位置。startIndex记录下一层从哪个位置开始枚举。组合和子集类问题需要它因为组合不关心顺序[1,2]和[2,1]是同一个组合通过强制下一层只能从当前元素之后开始选来避免重复组合。很多人的困惑在于什么时候用used什么时候用startIndex一句话总结每个元素可以被不同位置的递归层重复考虑但同一时刻只能用一次排列、元素不能重复使用的子集/组合→ 用used或startIndex。每个元素在不同层可以被重复选择同一个组合总和→ 用startIndex但进入下一层时不1。每个元素只有两种选择状态选/不选、大写/小写、左括号/右括号→ 不需要这两个变量直接带状态往下递归即可。后面我会结合具体题一个个过。2. 组合与子集startIndex 是这一类题的命门2.1 子集问题每次递归都记录先看最简单的一组子集类型。标题里的找出所有子集的异或总和再求和LeetCode 1863看起来很长拆开就是两件事先找出所有子集再把每个子集的异或总和加起来。如果只是枚举所有子集代码可以写成这样def subset_xor_sum(nums): n len(nums) res [] path [] def dfs(idx): res.append(path[:]) # 每个节点状态都是一个子集 for i in range(idx, n): path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return res注意我写的是res.append(path[:])这里如果写成res.append(path)最后结果会全是空列表。原因就是 path 在递归过程中被反复修改你 append 的是引用后面path.pop()会把已经存进去的内容也改掉。这个坑我刷题早期踩过 N 次现在已经是肌肉记忆了凡是把可变对象存入结果集合必须拷贝一份。回到 LeetCode 1863如果你先枚举子集再逐个算异或和也能 AC因为n最多 12复杂度 2^124096怎么算都很快。但我更建议你顺手做一个小优化在递归过程中直接维护当前子集的异或值每层把当前异或值累加到答案里省掉最后再遍历一遍子集的开销。def subset_xor_sum(nums): n len(nums) total 0 def dfs(idx, cur_xor): nonlocal total total cur_xor for i in range(idx, n): dfs(i 1, cur_xor ^ nums[i]) dfs(0, 0) return total这个写法里每个节点进入时cur_xor代表当前路径的异或值进入第一层时cur_xor0对应空子集恰好空子集的异或和是 0不影响结果。这个题有个更数学的做法是按位拆贡献但面试时用回溯已经足够还会显得你思路自然。2.2 组合卡住长度再收LeetCode 77 组合从1~n中选k个数。和子集的唯一区别是子集在每个节点都把 path 记录下来组合只在path 长度等于 k的时候记录。def combine(n, k): res [] def dfs(start, path): if len(path) k: res.append(path[:]) return for i in range(start, n 1): path.append(i) dfs(i 1, path) path.pop() dfs(1, []) return res这里start的作用是强制让数字按升序出现于是[1,2]会出现而[2,1]永远不会出现天然去重。这个题有个经典剪枝如果当前 path 的长度加上剩余可选数字个数都不足 k就没必要继续递归了。用公式表示就是if len(path) (n - i 1) k: break放在 for 循环里可以省掉大量无效递归。对 n20、k15 这种数据能明显感受到差异面试时主动提出来是加分项。2.3 组合总和允许重复选时下一层从哪开始LeetCode 39 组合总和候选数组无重复但每个数字可以被无限次选择。这题的代码只改一行进入下一层递归时从i开始而不是i1。def combination_sum(candidates, target): res [] path [] def dfs(start, remain): if remain 0: res.append(path[:]) return if remain 0: return for i in range(start, len(candidates)): path.append(candidates[i]) dfs(i, remain - candidates[i]) # 注意是 i不是 i1 path.pop() dfs(0, target) return res为什么从i开始就能允许重复因为当前选了candidates[i]之后下一层还能继续选它这就是无限使用的含义。而通过starti又保证了不会走回头路去选下标更小的元素避免了组合的重复。这里可以加一个剪枝先把 candidates 排序如果candidates[i] remain那么后面的元素全部大于 remain直接 break。因为候选数组里都是正数当前都放不进去了更大的更放不进去。这个剪枝在 target 很大、candidates 很长时效果非常明显。2.4 去重的本质同一层不放相同元素组合总和有个进阶版 LeetCode 40候选数组里含重复数字每个数字只能用一次。这种题必须先排序然后在 for 循环里加一行判断if i start and candidates[i] candidates[i - 1]: continue这一行的含义是在同一层递归中如果当前元素和前一个元素相等跳过。因为相同值的两个元素在同一层会产生完全相同的分支保留一个就够了。很多人的困惑是排序之后相邻重复元素被跳过会不会漏掉[1,1,2]这种需要两个不同位置的 1 同时出现的组合不会。因为跳过的是同一层的重复[1,1,2]里的两个 1 是分别在两层选中的不是同一层选了两次。仔细体会这句话同一层三个字是去重的核心边界。3. 排列问题全排列 II 为什么必须用 used 数组3.1 排列和组合在代码上到底差在哪组合用startIndex避免回头排列则不同——排列里每个元素都可能出现在任意位置。比如[1,2,3]的全排列第一个位置选了 2第二个位置还能选 1 或 3所以不能用startIndex限制从哪开始而必须用一个used数组标记哪些元素已经用过。LeetCode 46 全排列的基础代码def permute(nums): res [] used [False] * len(nums) def dfs(path): if len(path) len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) dfs(path) path.pop() used[i] False dfs([]) return res注意这里和组合类问题最大的代码差异循环每次都从 0 开始遍历但通过used数组过滤掉已经用过的元素。排列类型没有startIndex这是判断这类题型最明显的标志。3.2 used[i-1] 的两种判法有什么区别LeetCode 47 全排列 II在 46 的基础上允许输入包含重复数字。如果直接用 46 的代码会产生重复排列。去重手段和组合去重一样先排序 在同一层跳过重复元素但具体写法有两种。第一种写法if i 0 and nums[i] nums[i - 1] and not used[i - 1]: continue第二种写法if i 0 and nums[i] nums[i - 1] and used[i - 1]: continue两种写法都能去重但语义不同很多人在这里翻车。我建议你记住第一种也就是not used[i - 1]。它的含义是当前元素和前一个元素相同且前一个元素在刚刚的递归回溯中已经被撤销了说明当前是在同一层枚举重复值跳过。这个判断保留的是最左边那个相同的元素产生的分支其余重复元素在同一层直接剪掉。第二种写法used[i-1] True表示保留的是最右边那个相同元素的分支需要前一个元素处于使用中才允许继续。它也能去重但配合后续代码时如果其他剪枝条件写得不小心容易产生逻辑混乱。所以统一用not used[i-1]这种写法最稳。def permute_unique(nums): nums.sort() res [] used [False] * len(nums) def dfs(path): if len(path) len(nums): res.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) path.pop() used[i] False dfs([]) return res3.3 全排列 II 去重容易翻车的一个细节去重判断里必须是nums[i] nums[i-1]这个没问题但你必须保证数组是排序过的。如果你在原数组无序的情况下加同样的判断去重会失效还会误杀一些本应存在的排列。另一个容易翻车的地方是if used[i]: continue必须放在去重判断之前。因为如果当前元素已经被使用无论它是不是重复元素都得跳过这是第一道闸门。顺序反了虽然有时候结果也对但逻辑上是错的一旦数据集复杂bug 会非常难查。4. 字符串生成与形态转化把选择换个说法4.1 电话号码字母组合每层可选项由当前数字决定LeetCode 17输入一个数字字符串如 232 对应 abc3 对应 def返回所有可能的字母组合。这题的抽象方式和前面的数字组合完全一样区别只是每一层的候选集合不一样第 0 层的候选集由 digits[0] 决定第 1 层由 digits[1] 决定。所以代码里需要一个 index 记录当前处理到第几个数字for 循环遍历的是这个数字对应的字母。def letter_combinations(digits): if not digits: return [] mapping { 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz } res [] def dfs(idx, path): if idx len(digits): res.append(.join(path)) return for ch in mapping[digits[idx]]: path.append(ch) dfs(idx 1, path) path.pop() dfs(0, []) return res这段代码里没有used也没有startIndex因为每个字母只对应一种选择路径不需要互相之间避免冲突。这题的意义在于让你认识到回溯模板里的选择列表不一定是全局固定的它可以由当前递归层级动态计算。这是从数组组合跨越到字符串/其他复杂状态的桥梁。4.2 括号生成用剩余数量控制合法性LeetCode 22生成 n 对括号的所有合法组合比如 n3 时包括((()))、(()())等 5 个。这题如果先穷举所有括号序列再判断合法性2^(2n) 个可能性n10 就已经接近 100 万了性能不够优雅。更聪明的做法是在生成过程中就保证序列始终合法。合法括号序列有两个硬性条件左括号数量不超过 n。在任何一个前缀里右括号数量不超过左括号数量。把这两个条件转化成回溯的剪枝条件就是def generate_parenthesis(n): res [] def dfs(left, right, path): if len(path) 2 * n: res.append(.join(path)) return if left n: path.append(() dfs(left 1, right, path) path.pop() if right left: path.append()) dfs(left, right 1, path) path.pop() dfs(0, 0, []) return res注意if right left这个条件它保证任何时刻右括号数量不会超过左括号于是生成的每个前缀都是合法的。你不需要在最后检查括号匹配因为剪枝条件已经把非法路径全部干掉了。这题背后的思想其实可以推广到一类问题当某个选择会导致状态非法时直接在递归入口处拦截而不是生成完再验证。回溯的优势就在这里——你有机会在路径生长的过程中剪枝代价比事后验证小得多。4.3 字母大小写全排列跳过非字母位置LeetCode 784给一个字符串如 a1b2大写小写视为不同选择返回所有大小写组合a1b2、A1b2、a1B2、A1B2。核心点在于数字字符没有分叉必须直接进入下一层只有字母才分大小写两条路。def letter_case_permutation(s): res [] def dfs(idx, path): if idx len(s): res.append(.join(path)) return ch s[idx] if ch.isalpha(): path.append(ch.lower()) dfs(idx 1, path) path.pop() path.append(ch.upper()) dfs(idx 1, path) path.pop() else: path.append(ch) dfs(idx 1, path) path.pop() dfs(0, []) return res这个题其实比前面几道更直观地展示了决策树的样子数字节点只有一个孩子字母节点有两个孩子。如果字符串很长字母很多结果是 2^字母数量 种这正好提醒你回溯的时间复杂度一定是和叶子节点数量相关的。4.4 目标和把加减号当成选择LeetCode 494给你一个数组 nums 和一个目标 target你可以在每个数前面加或-求有多少种方案让总和等于 target。这题一眼看过去和排列组合没关系但它本质就是一棵二叉树每一层决定当前数字取正还是取负。直接回溯def find_target_sum_ways(nums, target): n len(nums) res 0 def dfs(idx, cur_sum): nonlocal res if idx n: if cur_sum target: res 1 return dfs(idx 1, cur_sum nums[idx]) dfs(idx 1, cur_sum - nums[idx]) dfs(0, 0) return res这个代码在 nums 长度比较小的时候能过但 nums 最长能到 30 的话2^30 种组合会直接超时。所以目标和其实更适合用记忆化搜索或者动态规划这也是下面要单独展开讲的部分。5. 从递归到搜索的思维跃迁拿目标和说说 DFS 记忆化5.1 纯回溯会超时问题出在哪以上一节的find_target_sum_ways为例纯回溯会把所有路径完整遍历一遍。你会发现很多子问题是重复的比如 nums[1,1,1,1,1]处理完前两个数后无论你是走11还是1-1-(-1)这里只是示意到达的状态(idx2, cur_sum某值)可能会被多条不同路径重复到达。每一次重复到达后面的 2^(n-2) 条路径都会被重新计算一遍浪费极其严重。递归树的重叠子问题一旦出现你就该想到记忆化。5.2 记忆化搜索在递归树上做缓存记忆化的写法非常简单把(idx, cur_sum)这个状态作为 key把从该状态出发能得到的方案数作为 value存到缓存里。下次再遇到同样的(idx, cur_sum)直接返回缓存结果。Python 里可以用functools.lru_cache代码改造成这样from functools import lru_cache def find_target_sum_ways(nums, target): n len(nums) lru_cache(None) def dfs(idx, cur_sum): if idx n: return 1 if cur_sum target else 0 return dfs(idx 1, cur_sum nums[idx]) dfs(idx 1, cur_sum - nums[idx]) return dfs(0, 0)这里的复杂度从 2^n 降到了 O(n * sum)因为状态总数就是 idx 的数量乘以 cur_sum 的可能取值范围。我在实际测试里跑过 nums 长度 30、target 任意的场景纯回溯需要几秒甚至更久记忆化版本毫秒级返回。5.3 另一种视角目标和转化成背包问题除了记忆化目标和还有一个非常经典的转化思路这也是面试中常见的追问点。设所有取正号的数之和为 P所有取负号的数绝对值之和为 N那么有P N sum(nums)P - N target两式相加得P (sum(nums) target) / 2于是问题变成从 nums 中挑出若干个数使它们的和等于 P求有多少种挑法。这就变回了标准的 0/1 背包求方案数问题或者说变回了组合总和问题。这个转化有两个先决条件(sum(nums) target)必须是偶数否则 P 不是整数直接返回 0P 必须是非负数。写成 DP 就是经典的背包思想这里我用回溯加记忆化写也能过def find_target_sum_ways(nums, target): total sum(nums) if (total target) % 2 ! 0 or total target 0: return 0 P (total target) // 2 lru_cache(None) def dfs(idx, remain): if remain 0: return 1 if idx len(nums): return 0 res dfs(idx 1, remain) if nums[idx] remain: res dfs(idx 1, remain - nums[idx]) return res return dfs(0, P)我个人很推荐把这两种解法都掌握回溯 记忆化是从搜索的角度理解问题转化成背包是从数学推导的角度理解问题。面试官如果问你能否优化你能说出这条转化链会是非常亮眼的表现。6. 刷题实战中的小坑基于我做这 8 道题的真实记录6.1 复制路径的时机append 进去的是引用还是快照这是回溯题最容易踩的坑没有之一。我在前面已经强调过一次res.append(path[:])而不是res.append(path)。原因再补一遍path 是递归过程中反复增删的同一个列表对象append 进 res 的只是引用。如果不拷贝等递归返回后 path 被 pop 成空res 里所有已经存进去的路径就全变成空列表了。path[:]是浅拷贝对一维列表足够。如果是二维路径比如解数独要存棋盘就得用深拷贝或者逐行拷贝。总之进结果集合之前想清楚这个对象后续还会不会被修改。6.2 剪枝不是可有可无的优化回溯题不剪枝在小数据量下和剪枝版本跑不出差异但一旦数据量上来差距是数量级的。我在刷组合总和的时候专门对比过candidates 长度 30、target 较大时不排序不剪枝的版本递归了 50 多万次排完序加if candidates[i] remain: break之后递归次数降到了几千次。这不是玄学是排序让当前选择放不下时后面所有更大值都可以直接放弃。剪枝的本质是利用数据的单调性或题目约束提前砍掉不可能产生答案的子树。写回溯题时养成一个习惯每次写完暴力版本先想想哪些子树是不可能走到答案的然后加剪枝条件。这个习惯在面试中比正确答案本身更能体现你的工程思维。6.3 组合总和 II和子集 II的去重逻辑是同一个LeetCode 40 组合总和 II每个数只能用一次和 LeetCode 90 子集 II含重复元素求不重复子集去重代码几乎一模一样都是排序后if i start and nums[i] nums[i - 1]: continue这个模式我强烈建议你单独摘出来背熟因为它出现的频率太高了。核心思想就是在有重复元素的组合/子集问题中保证同一层不枚举相同值。理解了这一句话这两道题加上全排列 II 的去重你就全部掌握了。6.4 时间和空间的复杂度直觉回溯题的时间复杂度通常等于决策树节点数空间复杂度等于递归深度。给你一个快速估算的参照表题目类型时间复杂度空间复杂度不算结果集子集枚举O(2^n)O(n)组合 C(n,k)O(C(n,k) * k)O(k)全排列O(n!)O(n)电话号码字母组合O(3^m * 4^k)m 是三字母数字个数k 是四字母数字个数O(mk)括号生成O(4^n / sqrt(n))卡特兰数相关O(n)目标和回溯O(2^n)O(n)面试中如果被问复杂度不要只说指数级最好能说出决策树的层数和分叉数然后解释为什么是这个量级。能讲清楚复杂度的来源说明你是真的理解了回溯的树形结构。6.5 回溯题的变体方向把这 8 道题刷完之后你其实已经掌握了回溯的大部分核心套路。后续再遇到以下题目本质都是同一套思路N 皇后每层放一个皇后用列、对角线数组判断冲突。复原 IP 地址每层切一段判断是否合法。单词搜索在二维网格上 DFS 找单词路径需要 visited 矩阵。分割回文串每层截取一段判断是否回文是则继续。火柴拼正方形 / 划分为 k 个相等的子集本质是组合问题加状态压缩剪枝。这些题在模板上没有跳出我前面说的框架只是在每层选择什么上做了更多文章。所以你把基础打牢后面刷题会越刷越顺。我在实际刷完这个专题之后最大的体会是回溯题的代码量都很短难的是把问题还原成决策树。你问我怎么训练这种还原能力我的建议是每道题先不要看题解自己画出递归树标清楚每一层的选择列表是什么、结束条件是什么、什么时候需要恢复现场。画个十道八道题之后再看到全排列组合括号这些关键词脑子里自动就会浮现树的形状代码自然就写出来了。这套方法比背代码模板有用得多因为模板解决的是语法层面的问题而画树解决的是思维层面的问题。后者想通了前者只是顺手的输出而已。
