1. 回溯算法最容易被低估的关卡组合与切割的底层逻辑刷题刷到代码随想录Day20三道题摆在一起看其实挺有讲究的39组合总和、40组合总和II、131分割回文串。很多人在这个节点上会突然卡壳因为前面刚熟悉了二叉树和递归的节奏一到回溯这里就发现脑子里的递归模板不够用了。先说个真实感受回溯本身不难难的是把握住它在每一道题里变形的那一层。组合总和里元素能重复取组合总和II里要求去重分割回文串里要切割字符串——本质上它们都在干同一件事从一堆选择里递归地挑选、尝试、撤销直到收集所有合法结果。这个尝试—撤销—尝试的过程就是回溯。这三道题特别适合放在一起刷的原因恰恰因为它们是从不同角度逼着你去理解同一个核心startIndex怎么传决定了你是求组合、求排列还是求切割。很多教程会把回溯总结成for循环里套递归这话没错但只有真正自己写过、调试过、被超时和重复结果折磨过之后才能体会这句话的分量。这篇文章我会按代码随想录的路线把这三道题从头到尾讲透。不光是贴解法还会把每道题背后的决策逻辑、剪枝优化、去重判断掰开来看最后附上我实际刷题时踩过的坑和调试心得。不管你是刚学完递归、准备啃回溯的新手还是已经刷过一阵子、想系统整理回溯思路的选手这篇文章都能给你一些实打实的收获。2. 先破除一个幻觉回溯不是暴力枚举这么简单很多人第一次接触回溯觉得这就是暴力解法——把所有可能都试一遍选出符合条件的。从结果上看确实如此但如果我们只停留在暴力这个认知层面后面遇到状态重置、去重、剪枝这些概念时就会一脸懵。回溯本质上是在一个决策树上做深度优先遍历。每一层递归对应一次做出选择的过程每一条路径对应一个候选组合。当一条路走不通或已经走完时我们就回退到上一个节点换一条路继续走。这个回退操作在代码里就是撤销上次的选择专业一点叫状态重置。这里要特别提醒一个问题递归本身是带记忆的函数调用栈保存了每一层调用的现场。回溯要找的恰恰是所有可能的现场所以每次进入下一层递归之前我们修改状态递归返回之后必须把这个状态恢复原样。不然的话上一次的选择会影响下一组组合的构造——这正是新手最容易出错的地方。举一个生活化的例子你收拾行李去旅行打算从衣柜里挑若干件衣服塞进箱子。回溯就相当于你一件一件往箱子里放放满或者不想放了就拿出来换另一件再放。这个过程里把某件衣服拿出来这个动作就是撤销没有它你的箱子永远是第一次装的组合。具体到代码模板上回溯的骨架极其固定def backtracking(参数): if 终止条件: 收集结果 return for 选择 in 本层可选集合: 处理节点做出选择 backtracking(更新参数) # 递归进入下一层 撤销处理回溯后面三道题都是在这个模板上演化出来的。记住这个骨架心里就有了底。3. 39组合总和允许重复选择后index的意义完全变了3.1 题目本质从选不选变成选几个39题的描述很直接给你一个无重复元素的整数数组 candidates 和一个目标数 target找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。和经典的组合问题相比最大的差异就是**可以重复选取同一个数字**。很多人的第一反应是让递归函数在每次调用时都从头遍历整个数组这样确实可以实现重复选取但结果里会出现顺序不同而内容相同的组合比如[2, 2, 3]和[2, 3, 2]这对组合问题来说是不合法的。正确的解法是每次递归传入index作为本轮遍历的起点但在递归调用时不传index 1而是仍然传index。这样做的含义是本轮选了candidates[i]之后下一轮依然可以从candidates[i]开始继续选从而实现了同一个数字的无限重复选取同时又因为遍历起点被锁定在index之后天然避免了组合顺序不同导致的重复。3.2 剪枝的核心先排序再判断能救你命如果不剪枝这道题对 target 较大的用例会直接超时。剪枝的思路很朴素在进入下一层递归前先判断当前累加和加上本轮选择的数字是否已经超过了 target如果超过了就直接continue因为数组已经从小到大排过序了后面的数字只会更大没必要再试了。这里有一个非常容易踩的细节剪枝条件必须放在 for 循环内部而不是放在递归函数的开头。放在循环内部时你可以利用数组已经排序的特性提前跳过后续所有更大的数字放在函数开头时你只能判断当前这一条路径是否还值得往下走完全没有发挥排序的优势。我见过不少代码把剪枝写成这样if sum(path) target: return放在递归函数第一行。这在效果上没有大错但它判断的是已经超了就整条路返回而排序循环内continue判断的是当前这个数字选了必超后面更大的数字更不必说两者在循环次数上有明显的效率差距。推荐写法是class Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: results [] candidates.sort() def backtrack(start_index: int, current_sum: int, path: List[int]): if current_sum target: results.append(path[:]) return for i in range(start_index, len(candidates)): if current_sum candidates[i] target: break path.append(candidates[i]) backtrack(i, current_sum candidates[i], path) path.pop() backtrack(0, 0, []) return results注意我用的是break而不是continue因为数组排过序了当前数字已经超了后面的必然也超。3.3 复杂度与递归深度别被指数级吓到组合类问题的复杂度通常写成 O(n × 2^n)其中 n 是 candidates 的长度2^n 是指数级的状态数n 是拷贝 path 的开销。空间复杂度是 O(target)主要由递归调用栈的深度决定。实际刷题时复杂度公式不需要背但要有一个直觉判断当 candidate 本身较小而 target 较大时路径会非常深递归调用栈也会很深。这时候如果剪枝条件写不到位超时几乎是必然的。我在 LeetCode 上跑过极端用例candidates [1], target 100不剪枝会陷入几乎无限递归剪枝后瞬间出结果。这个例子虽然极端但很能说明剪枝的价值。4. 40组合总和II去重才是回溯真正的分水岭4.1 去重的难点重复元素不能重复用但同一层也不能重复取值40题和39题的区别只有两个一是 candidates 里含有重复元素二是每个数字每个组合中只能使用一次。这两个条件叠加之后问题立刻复杂了。假设输入是candidates [1, 1, 2]目标值是 3。不去重的话[1, 2]会出现两次因为第一个 1 和第二个 1 都可以跟 2 组合。我们需要的是结果集里不能有重复组合但单个组合内部本身可以包含重复的数字比如[1, 1, 2]这种它内部有两个 1是合法组合。这就引出了回溯算法里最经典、也最容易把人绕晕的概念树层去重与树枝去重。4.2 用一棵树讲清楚树层去重和树枝去重想象一下递归实现过程中形成的决策树for循环每一轮遍历是在同一层节点上横向移动——这就是树层。每次递归调用是沿着某一条边纵深往下走——这就是树枝。在 40 题里[1, 1, 2]求目标 3 时第一次横向遍历会用第一个 1 作为起点纵向深入得到[1, 2]。第二次横向遍历如果还允许第二个 1 作为起点它又会得到[1, 2]。这就是树层重复必须跳过。纵向路径上比如[1, 1, 2]这个组合内部有两个 1它们是树枝上的两个不同节点完全可以共存。所以树层去重的判断条件是i start_index因为当前循环变量i如果大于本层起始位置start_index说明它和同一层上一个已用过的元素是兄弟关系需要比较是否值相同。代码核心如下class Solution: def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]: results [] candidates.sort() def backtrack(start_index: int, current_sum: int, path: List[int]): if current_sum target: results.append(path[:]) return for i in range(start_index, len(candidates)): if current_sum candidates[i] target: break if i start_index and candidates[i] candidates[i - 1]: continue path.append(candidates[i]) backtrack(i 1, current_sum candidates[i], path) path.pop() backtrack(0, 0, []) return results递归传的是i 1因为每个数字只能使用一次去重判断是i start_index and candidates[i] candidates[i - 1]因为需要跳过同一层上重复的值。4.3 used数组去重与排序去重的对比除了i start_index这种基于排序的去重方式还有一种常见的写法是引入used布尔数组在递归前后标记当前元素是否被使用过。两种方法都能正确去重但理解起来有差别排序去重更直观代码更短只需要一个排序和一行continue判断。used数组在排列问题如全排列 II中是必须的因为组合问题的start_index本身约束了遍历范围而排列问题没有这个约束。我的建议是做组合类题目时优先掌握排序去重的写法因为它代码量少思维负担低。但等做到排列问题比如 47题 全排列 II时一定要把 used 数组的写法补上否则会卡壳。其实这里隐藏了一个很关键的道理回溯的去重本质上是在同一层上做文章。理解了横向去重、纵向保留这八个字组合总和 II 就翻篇了。很多讲回溯的文章会用排序 相邻去重这种说法但这只说了一半另一半是为什么是相邻去重——因为排序后值相同的元素必然排在一起同一层上如果当前元素和前一个元素相等它俩产生的路径一定完全一样可以安全跳过。5. 131分割回文串切割问题的本质还是组合问题5.1 从选数字到切割线startIndex 的语义切换如果你觉得组合总和已经玩明白了那 131 题一定会让你重新审视回溯的能力边界。题目要求给你一个字符串 s将 s 分割成若干子串使得每个子串都是回文串返回所有可能的分割方案。第一次看到这道题很自然的问题是字符串怎么回溯切割线怎么表示答案是不要试图模拟切割这个动作而是把切割点想象成组合问题里要被选中的数字。在一个长度为 n 的字符串里相邻字符之间有 n-1 个可切割的位置。我们要做的就是在这些位置里选出一个子集使得每一段都是回文串。落实到代码里startIndex不再是数字数组的遍历起点而是当前这把切割刀放在哪个位置。每次递归进入下一层时startIndex指向当前子串的起始位置for循环里的i指向子串的结束位置。s[startIndex:i1]就是本次分割出来的子串检查它是不是回文串是就继续往下切不是就跳过。5.2 三个关键判断回文检查、终止条件、切割位置回文检查可以直接写一个双指针函数从两端向中间比较字符def is_palindrome(s: str, left: int, right: int) - bool: while left right: if s[left] ! s[right]: return False left 1 right - 1 return True终止条件很有意思当startIndex走到了字符串末尾等于len(s)说明整条路径上所有切出来的子串都已经验证过是回文串了这时把当前路径加入结果集。也就是说终止条件不是切了几刀而是切到了最后。完整的解法如下class Solution: def partition(self, s: str) - List[List[str]]: results [] def backtrack(start_index: int, path: List[str]): if start_index len(s): results.append(path[:]) return for i in range(start_index, len(s)): if not is_palindrome(s, start_index, i): continue path.append(s[start_index:i 1]) backtrack(i 1, path) path.pop() backtrack(0, []) return results5.3 切割回文串相比组合题多出来的那一层思维负担这道题真正难的地方不在于回文判断也不在于回溯框架而在于**把连续字符片段抽象成组合选项**的能力。刷题刷多了你会发现组合问题的选项是离散的元素而切割问题的选项是连续的子串。一旦能在脑子里把子串映射为从 startIndex 到 i 的一个闭区间切割问题就和组合问题没有本质区别了。有个小技巧可以辅助理解手动模拟时把字符串画成一排字母字母间的缝隙标上 0、1、2... 序号。startIndex是当前第一刀之前的位置i是这一刀切下去之后的位置。你会发现这个过程和从数组里挑数字惊人地相似——每一个切割点就是一个待选的数字只是选完之后要验证一下切出来的这段字符串是否满足额外条件回文。这也很自然地解释了为什么这类切割题目被归类在回溯下面而不是字符串处理题目下面。它考察的核心能力是如何枚举所有切割方案而不是如何判断回文。6. 三道题的复杂度对照与面试追问视角刷完三道题我建议你用表格把这几个维度横向对比一遍这是把零散知识内化成体系的好方法。题目元素可否重复选结果是否允许重复去重方式递归参数时间复杂度空间复杂度39组合总和可以不允许天然无重复递归传 iO(n·2^n)O(target)40组合总和II不可以不允许排序 树层去重递归传 i1O(n·2^n)O(n)131分割回文串不涉及不允许切割位置天然有序递归传 i1O(n·2^n)O(n)这个对比表很有用。你可以发现40题和131题虽然表面上一个在选数字、一个在切割字符串但它们的递归参数都是i 1因为它们都要求每个元素只用一次每个切割点只切一刀。而39题的递归参数是i目的就是为了允许重复选取同一个元素。面试时如果被问到回溯算法的时间复杂度为什么是指数级可以从两个角度回答一是决策树的节点数在最坏情况下是 2^n 量级每个节点都要尝试纳入或不纳入当前候选二是递归过程中每层需要拷贝路径数组带来额外的 O(n) 开销。至于 131 题最坏情况是字符串全由相同字符组成如aaaa此时任意一种切割都是合法的切割方案总数为 2^(n-1)每个方案还需要 O(n) 的时间复制路径所以整体是 O(n·2^n)。还有一点值得注意这三道题的空间复杂度都是 O(n) 数量级因为递归路径上只需要维护一条 path中间状态都保存在系统调用栈里。实际代码里path[:]拷贝进 result 的那步操作是额外开销千万别把它的复杂度漏掉。7. 我实际刷题踩过的坑调试顺序比调通本身更重要7.1 坑一result.append(path)只加了个引用结果全被清空了这是回溯新手最容易踩的坑没有之一。如果直接results.append(path)因为 path 是同一个列表对象在递归中被不断修改的最后 results 里存的其实都是同一个引用。等回溯完成时path 被弹回空状态results 里就只剩下一堆空列表。正确做法是results.append(path[:])。这里的[:]是复制列表的惯用写法在 Python 里等于浅拷贝。如果你写的是path.copy()或list(path)效果都一样但[:]是最地道的写法刷题场景下也最省打字。7.2 坑二剪枝条件放在了递归函数开头而不是 for 循环里前面 39 题已经详细讲过这个问题。很多文章里的模板会把当前和已经超过 target的判断放在递归函数最前面比如def backtrack(...): if current_sum target: return这个写法不是错的但效率明显不如在循环里判断current_sum candidates[i] target。差别在于前者是在多走一层递归之后才意识到路径超了而后者还没进入递归就直接放弃这个分支。对回溯这种本身就指数级复杂度的算法来说少一层递归就可能减少一个数量级的运算量。实际体验上candidates如果比较长比如超过 20 个元素两种写法在 LeetCode 上的耗时差距能到两三倍。7.3 坑三131 题的剪枝思路是先判断再入栈而不是入栈后判断切割回文串时很多人会把回文判断放在递归函数内部先把s[start_index:i1]加进 path进入递归后再检查它是不是回文不是就 return。这也能跑但结果是path 里会混入大量非回文子串的中间状态代码逻辑混乱且效率低。更好的做法是在 for 循环里先验证验证通过后真的认为这一段是合法的再把它加进 path、进入递归。这不仅是效率问题也是代码可读性的问题。回溯本来就是在正确与错误之间反复横跳的算法我们写代码时应该尽量让每个决策点只做一个判断别把所有判断都扔进递归里一锅炖。7.4 关于调试技巧打印递归树比打印每一步结果更管用回溯题调试时最容易看到的现象是输出结果顺序不对、数量不对、或者干脆是空的。这时候很多人的第一反应是单步跟踪但在递归密集的代码里单步调试效率奇低经常跟几步就晕了。我的习惯是在 backtrack 函数开头加一行带缩进的打印缩进深度用递归层数控制def backtrack(start_index, path, depth): print( * depth fstart_index{start_index}, path{path})把这行加进去跑一个小用例比如 candidates 只有 3 个元素的 39 题控制台上会直接打印出一棵完整的递归树。你一眼就能看出哪一层该进入循环却没有进入哪一层该 return 却继续往下走了。调试完之后把打印删掉即可。这个技巧对 131 题尤其有效因为切割问题的路径变化不如数字组合那么直观打印出每个节点尝试切出的子串能极大提高对算法运行过程的理解。8. 刷完这三道题回溯还有哪些延伸值得提前预告Day20 的这三道题做完你的回溯能力其实已经过了及格线。但要达到真正顺手的状态后面还有几个方向是必然会遇到的提前了解能少走弯路子集问题78题和组合问题的区别是组合只收集叶子节点子集要收集所有节点。理解这一点后你会发现代码几乎一样只是收集结果的位置不同。排列问题46、47题组合的核心是 startIndex 保证只看后面的元素排列必须每次从头遍历因此需要 used 数组来标记哪些元素已经在当前路径上。棋盘类问题51、37题回溯的经典收尾复杂度爆炸但仍然只能靠回溯硬解。这类题的难点在于状态表示和合法性判断本质上还是横向遍历选择 纵向递归深入。这三道题学完你对 startIndex 的设计、去重的两种手段、剪枝的位置选择、路径拷贝这四个核心点都应该有清晰的答案。之后遇到新的回溯题先想清楚这四个点代码基本就能直接写出来。最后分享一个我自己刷题时的习惯每道回溯题我都会拿笔在草稿纸上画一遍决策树标出哪些节点被剪掉了、哪些层被去重了。这个过程虽然费几分钟时间但比反复看题解有效得多。代码可以抄画树只能自己来而真正吃透回溯的那一刻往往就是你在纸上画出那棵树的时候。