刷《代码随想录》回溯篇刷到第三部分我猜很多人跟我一样是从“会背模板”过渡到“能做题”的这个阶段。前面的组合问题好歹能照葫芦画瓢到了切割、去重、排列这几类题同一个回溯框架却怎么都套不对劲。这篇就集中说说回溯里的进阶场景切割问题该怎么抽象、子集去重到底去的是什么重、排列和组合的本质差异在哪以及剪枝优化的度在哪里。这里的“回溯”指的是算法设计里的递归回溯法跟调试工具里看到的backtrace栈回溯、ARM调用栈回溯完全是两码事别搞混了。如果你已经掌握了回溯的基础模板正在被重复元素的去重和IP地址切割这类题目折磨这篇应该能给你一些可以直接抄作业的思路。1. 切割问题本质上是“切点组合”不是字符串问题很多人一看到“分割回文串”“复原IP地址”这种题就犯怵觉得字符串的切割操作很复杂。其实你只要把切割抽象成“选切点”就会发现它跟组合问题是一模一样的结构。组合问题是在一个数组里选几个数切割问题是在字符串的空隙里选几个位置下刀——选出来的切点集合本身就是一组组合。1.1 把切割抽象成“在空隙中选切点”以LeetCode 131分割回文串为例给你一个字符串s要求分成若干子串每个子串都是回文串。你不需要真的去模拟“切”这个动作只需要想清楚整个字符串有len(s)-1个空隙每个空隙可以切也可以不切。回溯的每一层递归就是决定“下一个切点选在哪里”。这里有个关键的参数设计递归函数里始终带着一个startIndex表示当前从原字符串的哪个位置开始找下一个子串。for循环从startIndex遍历到字符串末尾每一轮枚举的i代表当前子串取s[startIndex:i1]这一截。也就是说startIndex是上一刀的下一刀起点i是这一刀的落刀位置。每一刀落下就把[startIndex, i]这段字符作为一个子串处理。我在刷这题时最开始的错误是把它当成“逐字符判断回文”然后在递归里传一个拼接后的新字符串结果状态变量越来越多剪枝也写不明白。后来想通了不要试图在递归里维护“已经切割好的字符串列表”之外的东西路径就存已经切出来的子串列表递归深度到了startIndex走到末尾就把路径加入结果。代码干净很多def partition(s): res [] path [] def backtrack(startIndex): if startIndex len(s): res.append(path[:]) return for i in range(startIndex, len(s)): sub s[startIndex:i 1] if sub sub[::-1]: # 是回文才走这条分支 path.append(sub) backtrack(i 1) # 下一刀从 i1 开始子串不重叠 path.pop() backtrack(0) return res这段代码里判断回文用了最简单的切片反转比较刷题够用。你真正需要吃透的是为什么递归参数是i 1而不是startIndex 1因为当前子串已经占到了位置i下一刀必须从i的后一个空隙开始否则子串就重叠了。1.2 切割问题的终止条件、截取边界和合法性校验同样是切割复原IP地址LeetCode 93比分割回文串多两个难点一是每一段必须是0到255之间的数字二是恰好要切成4段。多出来的其实不是“切割逻辑”而是“什么时候停止切割”的判断——这依然是终止条件的变体。分割回文串的终止条件是startIndex len(s)意味着整串已经切完。复原IP地址的终止条件多了一层当path已经收集了4段但startIndex还没到字符串末尾说明切多了这层递归直接返回如果path正好4段且startIndex len(s)才加入结果。这个条件一定要写成联合判断我见过不少写法把“凑够4段”和“切完整个字符串”分开判断结果出现“只切了3段也进结果集”的bug。截取边界也是切割题的常见坑。比如判断IP段合法性时s[startIndex:i1]如果以0开头且长度大于1比如“012”这是不合法段还有数值超过255的情况。更隐蔽的是i越界问题for循环里range(startIndex, len(s))当子串长度超过3时其实可以直接跳过因为IP段最长也就3位数字。这个剪枝后面会详细说但在切割题里边界条件常常是AC与否的分水岭。我建议把切割问题的代码模板单独整理成一个范式def cut(s): res, path [], [] def backtrack(startIndex): if 终止条件成立: res.append(path[:]) return for i in range(startIndex, len(s)): sub s[startIndex:i1] if 合法性校验通过: path.append(sub) backtrack(i 1) path.pop() backtrack(0) return res切割回文串、复原IP地址、甚至一些自定义的字符串拆分题套这个范式都能跑。唯一要动脑子的就是“终止条件”和“校验函数”这两处。想明白切割问题的本质是切点组合字符串长度、段数限制都是外加的终止约束就不会再被题目吓住。2. 子集问题的收集时机与去重的真正含义子集问题LeetCode 78看起来比组合简单因为每个元素都有“选/不选”两种状态但很多人在写代码时傻眼为什么组合问题在叶子节点收集结果子集问题却每层都要收集答案很简单子集问题收集的是“所有合法的节点状态”而不是“满足特定长度的路径”。2.1 子集问题为什么在每一层都收集结果组合问题的落点是“选k个元素的组合”你必须等路径长度达到k才算一个答案所以只能在叶子节点收获。子集问题没有长度限制任何前缀都是子集。从递归树来看根节点是空集第一层是每个元素作为开头的单元素子集第二层是两个元素的子集……每一层节点的状态都是一个子集因此每次进入递归时就要把当前path存进结果。这里有个特别容易错的点res.append(path[:])和res.append(path)的区别。如果你直接append(path)后续递归里的pop操作会把这个列表原地修改导致结果集里所有子集最后都变成空列表。我在刚学Python刷题时踩过这个坑排查了半天才发现是引用传递的问题。切片复制path[:]是复制内容这样快照才不会被后续操作污染。def subsets(nums): res [] path [] def backtrack(startIndex): res.append(path[:]) # 每一层都收集包括空集 for i in range(startIndex, len(nums)): path.append(nums[i]) backtrack(i 1) path.pop() backtrack(0) return res很多题解会把“空集”单独提出来处理其实不用。第一次进入backtrack(0)时path是空的res.append(path[:])已经收集了空集for循环再从第一个元素开始扩展。这个设计的巧妙之处在于每个节点先把自己存入结果再去生成子节点天然覆盖了所有前缀。2.2 树层去重 vs 树枝去重同一个used数组的两种读法子集IILeetCode 90在子集基础上加了“可能包含重复元素”的条件题目要求返回的子集中不能有重复组合。比如[1,2,2]你如果正常跑回溯会出现[1,2]两次因为两个2是一样的值但不同位置。去重的核心概念是“树层去重”和“树枝去重”这两个术语我一开始总搞混直到把递归树画出来才彻底明白。所谓的“树层去重”指的是在for循环的同一层里如果前一个元素已经被处理过且当前元素和前一个元素值相同那就跳过当前分支。用used数组标记的话条件就是i 0 and nums[i] nums[i-1] and not used[i-1]。这里的not used[i-1]表示前一个元素在递归回溯后已经被释放说明“同一个for循环里”上一次迭代处理过相同值的元素了如果used[i-1]还是True说明前一个元素还在当前递归路径上那是“树枝去重”的情况不能跳过。场景used[i-1]状态应该怎么做同一层for循环遇到重复值False已被释放跳过避免同一层重复组合同一递归路径上遇到重复值True还处于占用状态不跳保留不同顺序的合法组合还是以[1,2,2]为例第一层选了第一个2递归进去处理[2]回溯后第二个2进入第一层for循环此时前一个2已经释放used[1]False如果nums[1]nums[2]说明第一层出现了重复元素跳过。但是第一个2在递归路径里遇到第二个2时used[1]True说明那是“同一个组合里选了另一个相同值的元素”这个分支不能跳。用排序加used数组是比较直观的写法不过《代码随想录》里也提到过另一招不需要used数组直接比较i startIndex and nums[i] nums[i-1]。这个写法的前提同样是数组已排序。i startIndex能区分当前是在同一层for循环i大于startIndex而不是递归进入下一层后的第一个元素。我两种写法都试过个人觉得used数组更通用因为它在排列问题里还要承担另一个职责后面会讲到提前熟悉它的语义没坏处。2.3 实际刷题中我去重踩过的坑把树层去重写进递归边界分享一个我真实犯过的错误。有一次写子集II的去重我想着“既然要去重干脆在递归函数开头判断if i startIndex and nums[i] nums[i-1]: return”。这个思路看着合理但实际运行结果会漏掉大量合法子集。原因是把去重逻辑放在递归边界会把“子节点里的第二个元素与子节点里的第一个元素相同”这种树层重复错误地当成“路径里的合法重复”结果连[1,2,2]这种包含重复数字本身的合法子集都被跳过了。正确的做法是在for循环内部进入递归之前判断去重。用伪代码表示就是for i in range(startIndex, len(nums)): if i startIndex and nums[i] nums[i-1]: continue path.append(nums[i]) backtrack(i 1) path.pop()去重判断只负责“跳过当前这一层里已经出现过的值”递归内部该收集的还是正常收集。记住这个区分子集去重基本就不会再出错了。3. 排列问题不用startIndex但used数组带来了新变化排列和组合最大的区别在《代码随想录》里反复强调过排列是有序的[1,2]和[2,1]是两个不同的结果。因为顺序有意义所以递归时不能像组合那样用startIndex锁住后面的元素而要从头开始选。这就是为什么排列问题的递归参数里没有startIndex取而代之的是一个贯穿整条路径的used数组。3.1 used数组在排列中的双重职责组合问题里used数组只有一个职责去重。排列问题里used数组承担两件事既标记“当前路径上哪些元素已经用过”又参与重复值的去重判断。以全排列LeetCode 46为例递归函数每层都从0开始遍历nums但只有not used[i]的元素才能选。这样保证了一条路径上每个元素只用一次同时天然避免了回头选已经选过的元素。def permute(nums): res [] used [False] * len(nums) path [] def backtrack(): 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]) backtrack() path.pop() used[i] False backtrack() return res组合问题的for循环从startIndex开始是怕回头把同一个元素再选一次排列问题从头开始则是为了让每个位置都能尝试所有没被用过的元素。两种设计各有逻辑别混着来。如果你在排列问题里加了startIndex就会漏掉大量排列因为子递归必须从过去没用过的元素里重新选择而startIndex限制了选择范围。3.2 排列去重去重判断和used数组的状态要配合好全排列IILeetCode 47在数组里加了重复元素这时候used数组的两种角色会打架。去重条件写成if i 0 and nums[i] nums[i-1] and not used[i-1]时我一开始很困惑递归里明明已经对每个元素做了used[i]占用标记为什么还要这个not used[i-1]原因在于排列问题里同一个数字可能在不同递归深度出现。比如[1,1,2]第一层选了第一个1第二层选了第二个1这是合法排列[1,1,2]但第一层选完第一个1并回溯后第二层再选第二个1此时第一个1已经释放used[i-1]为False如果再选第二个1就会在“同一树层”上制造重复排列。not used[i-1]正是用来区分“前一个1还在路径中属于树枝上合法重复”和“前一个1已经释放属于树层上非法重复”这两种情况。这个题是所有回溯题里最能考验对used数组理解程度的题目。写代码时最容易犯的错误是把not used[i-1]写成used[i-1]结果完全反了要么漏解要么死循环。我自己的排查方法是遇到这种题别急着写代码先手动画递归树把每一层的used数组状态标出来再对比代码逻辑几轮下来就通了。3.3 排列递归树要点终止条件与结果收集时机排列问题的终止条件是len(path) len(nums)因为只有一个排列塞满了所有元素才是一个答案。但注意有一个隐性约束如果nums长度为n那么递归深度一定是n不用额外剪枝因为used数组已经保证每个元素最多被选一次。结果收集时机在叶子节点这点和组合问题一致。不过排列问题的叶子节点数量是n!数据规模稍大一点就很可观。LeetCode上全排列的输入长度也就6到8超过8的测试用例很少但如果实际项目中要做全排列一定要评估数据规模n10就已经有362万条结果了内存和耗时都会暴涨。刷题阶段不需要过度优化但心里要有这个数。4. 剪枝优化哪些该剪哪些剪了反而坏事回溯的性能问题是教科书里老生常谈的话题每层for循环都可能需要遍历剩余的所有元素如果不剪枝组合类问题的时间复杂度经常是组合数量级数据一大就超时。但剪枝不是无脑加条件《代码随想录》的题解里多次强调剪枝的思路是“提前终止必然不可能产生答案的分支”。这句话看起来简单实际判断时有很多细节。4.1 最常用的两处剪枝for循环上限和剩余元素数判断以组合总和IIILeetCode 216为例题目要求从1到9中选k个数和为n。不剪枝的写法是for循环从startIndex到9每次递归都尝试所有可能。但这题有一个明显的剪枝点如果当前path长度已经接近k剩余可选的数不够凑满k个这个分支可以直接终止。具体到for循环上限def combinationSum3(k, n): res [] path [] def backtrack(startIndex, remain): if len(path) k: if remain 0: res.append(path[:]) return # 剪枝1for循环最大到 9 - (k - len(path)) 1 # 因为还需要 k-len(path) 个数后面至少要留出这么多位置 for i in range(startIndex, 9 - (k - len(path)) 2): if remain - i 0: break # 剪枝2剩余和已经不够减 path.append(i) backtrack(i 1, remain - i) path.pop() backtrack(1, n) return res第一处剪枝是“剩余位置不足”假设k3当前path长度为1还需要2个数。for循环的i最多能到9 - (3 - 1) 1 8因为从9开始往前数两个位置i如果取9剩余的可选数只有0个9后面没有数了凑不齐2个数。所以i的最大值是9 - (k - len(path)) 1即“从当前可选最大值往回退需要的计数个数”。这里的 1是因为range右边界是开区间。第二处剪枝是“剩余和不足”把remain当成一个不断减小的目标值如果remain - i 0说明当前i已经把剩余目标值减成负数了那么更大的i更不可能直接break跳出for循环。这个剪枝在组合总和LeetCode 39那题里更明显因为那题不限制数字个数剪枝思路变成先排序一旦当前数字大于remain就break。4.2 剪枝前先搞清楚三件事排序、负数、恢复现场剪枝最容易出问题的场景是数组里有负数。组合总和这类题如果数组包含负数排序后if nums[i] remain: break这个剪枝就是错的因为后面可能有负数把和拉回来。比如nums[2, -1, 3]目标是02大于0但2加-1再加-1等于0你不能在2那里就break。遇到包含负数的题目要么放弃这类剪枝要么改用完全不同的搜索策略不能硬套。另一个隐蔽问题是剪枝条件可能导致“漏解但不报错”。你剪掉的分支其实可能包含合法结果只是测试用例没cover到。我的经验是先用最朴素的、不加任何高级剪枝的版本把AC拿到再逐步加剪枝每次加完都重新跑一遍之前的测试用例对比结果集是否完全一致。这样做既保证正确性又能衡量剪枝的实际收益。4.3 剪枝收益的实测对比什么时候值得剪我实际测过组合总和III两种写法的耗时差异。输入k3, n9不剪枝版本大概要跑0.8毫秒加上两处剪枝后是0.2毫秒左右看起来不错。但输入缩小到k2, n5时剪枝前后都是0.1毫秒以内差异可以忽略。剪枝真正的价值体现在大搜索空间上比如k4, n20这类用例不剪枝可能要遍历几百条路径剪枝后只遍历几条。所以我的建议是刷题阶段不纠结剪枝代码的优雅性先保证能用回溯模板把题解出来。剪枝优化适合在“提交超时”之后再来做而不是在一开始就想着把所有剪枝条件写进去。过度设计剪枝条件会增加代码的复杂度反而容易引入隐蔽bug。LeetCode的测试数据量通常不大很多回溯题不剪枝也能AC真正需要剪枝的一般是combination sum II、permutation这类会给出较大输入范围的题目。剪枝还有一个容易被忽略的好处递归深度的减少能大幅降低内存占用因为每层递归的函数调用栈会保存局部变量深度越大栈占用越高。这是算法层面的事情跟调试工具里说的“栈回溯”不是一回事但理解递归调用栈的深度成本会让你在写回溯时更有意识地控制递归层数。5. 从模板到实战回溯题的四个追问《代码随想录》里的回溯题解核心其实就一句话明确递归函数的参数、终止条件、单层搜索逻辑。但实际做题时你会发现模板背得再熟遇到新题还是不知道参数该怎么设。我自己的方法是把每个题套进四个追问里这个问题是把“选择”抽象成什么是选数字、选切点、还是选排列位置递归树的每一层在做什么是枚举剩余元素还是枚举剩余切点还是从头枚举所有没用过的元素结果应该在哪里收集是叶子节点、每个节点、还是满足特定条件时重复问题出现在树层还是树枝去重条件怎么写才不影响树枝上的合法解以这四个追问去拆题组合问题、切割问题、子集问题、排列问题看着千变万化但底层就那几种模式。我自己的体会是回溯这个章节刷到后面真正困难的不是模板而是模式识别——看到一个陌生题目能迅速判断它属于组合类、排列类还是子集类再决定用不用startIndex、要不要used数组、在哪里收集结果。比如“括号生成”LeetCode 22这种题看起来和数字组合没关系但它本质上是“在n对括号的排列中筛选合法序列”左括号右括号的选择就是一个典型的排列回溯。又比如“单词搜索”LeetCode 79是在网格里做深度优先的路径搜索同样是回溯的变体区别只是选择列表变成了“上下左右四个相邻格子”。看穿了这一点不同题目间的壁垒就没有那么高了。我把刷过的回溯题整理过一张表组合类、分割类、子集类、排列类、棋盘类各自的高频题号和核心差异点写完这张表再刷题思路会清爽很多。这五个类别的模板你都可以从《代码随想录》里找到对应章节但请务必自己把递归树画一遍尤其是树层去重和树枝去重的区别光看题解很难内化。回溯这一篇写下来信息量确实不小。第三部分的几个重点——切割问题的切点抽象、子集去重的两种写法、排列里used数组的双重职责、剪枝的收益判断——都是刷题时真正卡过我的地方。如果你正在刷这一章建议按这个顺序来先搞懂切割题和子集题再去碰排列和剪枝。把每一题的手动递归树画出来注意标注各层的used状态变化比多刷十道题都管用。