1. 今日算法从两道题吃透回溯与剪枝周一早上的算法打卡我选了“回溯算法”和“回溯剪枝”这一组题。力扣77组合和力扣216组合总和III前者是回溯的入门模板题后者是带约束条件的变体两道题连刷一遍基本上能把回溯的套路框架、剪枝思路、边界处理都摸透。先说结论如果你打算刷回溯专题77和216这一对题非常适合作为起步组合。77让你理解“回溯是什么、递归树长什么样、结果怎么收集”216在77的基础上加了一个“和为目标值”的约束逼着你思考怎么在搜索过程中提前砍掉无效分支——也就是剪枝。这两道题刷明白后续再遇到全排列、子集、分割回文串、N皇后这些题你会发现自己已经有了一个可以复用的框架。阅读对象就是正在刷力扣的算法学习者尤其是刚接触回溯、对递归树和剪枝边界比较懵的朋友。下文会给出完整的推导过程、代码逐行注释、剪枝条件的数学解释以及我踩过的坑保证是能直接抄作业的那种。2. 回溯算法的核心框架与两种不同层级的剪枝思路2.1 回溯的本质在一棵隐式树上做深度优先搜索回溯算法听起来很高深拆开来看其实就六个字走不通就回头。你要做的是在一棵“隐式树”上做深度优先搜索每到一个节点尝试一种可能的选择然后往下一层走如果发现这条路走下去不可能得到答案或者已经把所有可能性都试完了就撤销这次选择回到上一个节点换一条路继续走。拿力扣77来说题目是给定1到n这n个整数返回所有可能的k个数的组合。比如n4、k2答案是[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]。这里有一个新手最容易晕的地方组合和排列的区别。组合不关心顺序[1,2]和[2,1]是同一种组合。在代码里实现“不重复”的方式就是每次递归时只从当前元素的后面去选也就是维护一个startIndex起始位置。第一层选了1第二层只能从2开始选选了2后面只能从3、4里选。这样就天然避免了[2,1]这种逆序组合的出现。把上面这个过程画成树大概长这样[] / | | \ 1 2 3 4 / | \ / | | 2 3 4 3 4 4每个叶子节点就是一个长度为2的组合。回溯算法做的就是把这棵树完整地遍历一遍每走到一个合法的叶子节点就把路径加入结果集。2.2 回溯三步走模板参数、终止、单层逻辑刷多了回溯题之后你会发现代码结构高度一致完全可以总结成一套模板。记住下面这个三步走结构能解决绝大多数回溯问题第一步确定递归函数的参数。一般情况下需要三个参数原数据范围比如n、目标长度比如k、以及当前搜索的起始位置startIndex。另外最好有一个局部变量path记录当前路径以及一个结果集result。第二步确定终止条件。对于组合问题当path的长度等于k时说明已经选够了k个数把path的拷贝加入result然后return。第三步确定单层搜索逻辑。使用for循环从startIndex遍历到n每轮做三件事把当前数字i加入path递归调用注意startIndex要传i1递归返回后撤销选择把数字i从path中弹出。这一套“加入-递归-撤销”的动作就是回溯的精髓。很多新手会忘记第三步里的“撤销”动作结果导致path越来越大输出的结果全错。我个人想强调一点撤销是回溯的灵魂。没有撤销递归就只是普通的DFS而不是回溯。你可以把path想象成一个栈递归的时候压入元素返回的时候弹出元素这样才能保证不同分支之间互不干扰。2.3 剪枝的两个层次可行性剪枝与最优性剪枝聊回剪枝。剪枝的本质就一句话在递归还没有走到叶子节点之前提前判断这条路有没有继续走下去的必要。如果有必要就继续没必要就停在这里直接return省掉整棵子树的计算。剪枝一般分两个层次第一层是可行性剪枝也是最常用的一种。当前的选择和已走过的路径加在一起已经注定不可能满足目标约束直接停止。比如216题里目标是组合的和等于n那么如果当前path的和已经大于n无论后面再加什么数字和只会更大所以根本不用往下递归。这一刀砍下去整个分支瞬间消失。第二层是边界范围剪枝。当前可选的数字范围已经不够凑满k个了比如n4k4我已经选了第一个数2path里只有一个数还需要3个而startIndex已经到3了后面只有3、4两个数可选根本凑不够4个。这时候就可以不进入循环直接return。77题的剪枝属于第二层216题的剪枝则两层都需要用上。这两类剪枝的逻辑不冲突可以叠加使用实际刷题时经常同时上。3. 力扣77组合普通回溯实现与剪枝优化版本的手把手讲解3.1 普通做法先把回溯框架跑通先看最朴素的写法不包含任何剪枝。这个版本的价值在于让你先把思路理清楚不要被细节干扰class Solution: def combine(self, n: int, k: int) - List[List[int]]: result [] path [] def backtrack(startIndex: int) - None: # 终止条件path长度等于k收集结果 if len(path) k: result.append(path[:]) return # 单层搜索从startIndex开始尝试每个数字 for i in range(startIndex, n 1): # 做选择 path.append(i) # 递归下一层起始位置变为i1防止重复组合 backtrack(i 1) # 撤销选择 path.pop() backtrack(1) return result这段代码应该逐行理解不要死记硬背。path[:]这一步是关键它做了列表的拷贝。如果直接result.append(path)后续path.pop()会把已经加到result里的内容一并改掉。很多新手在这里翻车打印出来发现结果集全是空列表或同一个列表就是因为没有拷贝。backtrack(i 1)这行是保证组合不重复的核心。因为下一层只能取比当前元素更大的数所以不会出现[2,1]这种重复组合。这个版本的时间复杂度是O(C(n,k) * k)也就是组合数乘以每次拷贝路径的开销。空间复杂度是O(k)递归深度为k每层存一个数字。3.2 剪枝优化版为什么循环上界是n - (k - len(path)) 1接下来是剪枝版本代码变化就一处但这一处非常关键class Solution: def combine(self, n: int, k: int) - List[List[int]]: result [] path [] def backtrack(startIndex: int) - None: if len(path) k: result.append(path[:]) return # 剪枝i最多只能走到 n - (k - len(path)) 1 for i in range(startIndex, n - (k - len(path)) 2): path.append(i) backtrack(i 1) path.pop() backtrack(1) return result这个剪枝条件里有个很经典的公式i n - (k - len(path)) 1。怎么理解假设n4k3当前path里已经有1个数了还需要再选2个k - len(path) 2。如果当前startIndex已经是3那后面只剩下3、4两个数可选刚好够如果startIndex是4后面就只剩一个4凑不满3个肯定没结果。公式里的k - len(path)表示“还差几个数才能凑满”n - (k - len(path))表示“从第几个数开始选才能保证后面有足够的数字”。比如还差2个数n4那么n-22意思是至少要留下2个数字供后面选择所以最多只能从2开始选选完2后面还有3、4两个数可用。如果是4那已经到顶了后面没数了。所以for循环的上界是n - (k - len(path)) 1因为range是左闭右开区间要取到n - (k - len(path)) 1这个值Python的range应该写n - (k - len(path)) 2。这里差一错误极其常见建议写的时候在纸上画一画。这个剪枝看起来只是缩小了循环上界但实际效果很可观。最极端的情况是n100、k50普通做法第一层循环要遍历100次而剪枝后第一层最多遍历到51就停止了差不多省了一半的搜索空间。递归层数越深这种省下来的分支成指数级放大。3.3 复杂度对比与实际运行体会版本递归遍历的节点数时间复杂度适用场景普通回溯整棵递归树全部遍历O(C(n,k) * k)数据范围小如n≤20剪枝回溯递归树末端部分分支被砍掉O(C(n,k) * k)但实际搜索节点数显著减少n和k接近时效果尤其明显这里有个容易误会的点剪枝并不会改变算法的最坏时间复杂度。因为最坏情况下如果所有分支都有效剪枝一个都剪不掉复杂度还是组合数级。但在实际数据中尤其是n和k都比较大的时候剪枝带来的收益是肉眼可见的。我实测过n30、k15的情况普通版本要跑几秒剪枝版本几十毫秒就出结果差距有几十倍。所以我的建议是平时练习先写普通版本把框架跑通再优化成剪枝版本。直接一上来就写剪枝版本很容易被边界条件绕晕反而理解不了回溯本身。4. 力扣216 组合总和III在组合框架上加两个约束条件4.1 题目本质与约束条件解析力扣216的题目是找出所有相加之和为n的k个数的组合且满足以下条件组合中只使用1到9的数字且每个数字最多使用一次。返回值中不能包含重复组合组合内数字可以按任意顺序。比如k3n7答案是[[1,2,4]]k3n9答案是[[1,2,6],[1,3,5],[2,3,4]]。对比77题这里的变化有两点第一搜索范围固定为1到9不再是1到n第二多了一个和等于n的约束。这意味着77题里“收集结果”只看长度是否等于k而216题不仅长度要等于k和还必须等于n。多了这个约束之后剪枝的空间更大了。搜索范围从1到9反而让递归树的规模变小了因为总共只有9个数字可选树的深度最大也就是9。但是注意k可能很小比如k2而n17那么需要从1到9里选两个数相加为17只有(8,9)这一对。这种情况下如果不用任何剪枝还是会把所有两两组合都遍历一遍然后筛选出符合条件的。剪枝之后搜索空间可以进一步压缩。4.2 完整代码实现含两层剪枝class Solution: def combinationSum3(self, k: int, n: int) - List[List[int]]: result [] path [] current_sum 0 def backtrack(startIndex: int) - None: nonlocal current_sum # 剪枝1当前和已经超过目标n直接返回 if current_sum n: return # 终止条件长度达到k判断和是否等于n if len(path) k: if current_sum n: result.append(path[:]) return # 剪枝2剩余数字不足以凑满k个 # 还有一个隐含的剪枝用最大的数字尝试后如果current_sum加上剩下的最大和都凑不够n也可以剪掉 max_possible 9 - (k - len(path)) 1 for i in range(startIndex, max_possible 1): # 做选择 path.append(i) current_sum i # 递归下一层 backtrack(i 1) # 撤销选择 current_sum - i path.pop() backtrack(1) return result这个版本有两处剪枝第一处是current_sum n的检查放在递归函数的开头。因为组合里的数字都是正数每加一个数字和只会变大。如果当前和已经大于n无论继续加多少都不可能等于n所以可以直接返回。这一刀非常有效因为很多分支会在早期就发现和超了省掉的递归是整棵子树。第二处是循环上界的推导和77题的剪枝一模一样的思路。k3当前path长度为1还需要2个数搜索范围最大到79-217循环从startIndex遍历到7即可。因为如果当前选了8后面只剩9一个数可选凑不齐3个。4.3 范围上限的推导用生活逻辑来理解很多人记不住9 - (k - len(path)) 1这个式子我用一个生活化的例子解释。假设你要在1到9这9个数字里选3个组成一个组合已经选定了第一个数是7。后面还需2个数但可选范围只剩8、9两个。你从8开始选也行从9开始选也行刚好够。但如果当前已经选到8后面只剩9一个数无论如何凑不齐3个数字了。所以“最早能开始选的位置”得保证从这个位置开始一直选到9数字个数不少于还需要的个数。用数学表达就是max_possible 9 - (k - len(path)) 1。换句话说当len(path)越接近kmax_possible就越往后退搜索空间越小。等path长度接近k时循环往往只剩一两个可选项递归树的末端分支非常稀疏。这个推导过程同样适用于77题把9换成n即可。两道题放在一起对比刷效果非常好因为你可以直观看到同一个剪枝公式在两个题目里用法完全一致。4.4 216题的两个坑数字范围忘了截止和超了还在递归第一坑搜索范围写错。有人把216题的循环写成从startIndex到9没问题但有人误写成从startIndex到n如果n大于9循环就会越界。记住这里可选数字是1到9不是1到n。数字范围是固定的不是题目给的n。第二坑和超了没有及时剪枝。如果不做current_sum n的检查很多分支会一直递归到长度等于k才发现和不对白白浪费大量计算。尤其是n比较小比如n5的时候大部分分支其实在第二三层就已经和超了不剪枝的话会多做很多无用功。这个坑还有一层隐蔽性如果你把“和超过n”的判断放在“长度等于k”之后那么即使当前和已经超了代码还是会把path递归到k层然后才发现和不对。正确的做法是把current_sum n放在递归函数开头先判断再往下走。5. 实操路上的五个常见问题与排查实录5.1 为什么结果集里全是一样的列表这是回溯新手最常见的翻车现场。代码写完了运行一看result里所有元素都是同一个列表比如[[], []]之类。原因是result.append(path[:])写成了result.append(path)。Python的列表是引用类型path这个变量指向的是一个内存地址。你append到result里的是引用而不是内容的拷贝。回溯逻辑会在递归返回时反复执行path.pop()每次都能改掉path的内容。由于result里所有元素都引用同一个path最终它们展示出来的内容就是path最后一次被覆盖后的状态。解决方案就是拷贝result.append(path[:])或result.append(list(path))。这一个坑我当年至少踩过三次每次都是打印调试才发现。你可以在代码里临时加一行print(fappend result: {path[:]})和print(fresult now: {result})肉眼看一下就明白了。5.2 startIndex到底是干什么用的什么时候从1开始startIndex的作用是标记“这一层从哪个数字开始搜索”。组合问题里必须带startIndex否则会出现重复组合。比如第一层选1第二层可以选2、3、4如果第一层选2后第二层仍然从1开始选就会出现[2,1]而[2,1]和[1,2]是同一个组合。在77题中因为数字范围是1到n初始调用当然从1开始。但如果你把初始调用写成backtrack(0)for循环range(0, n1)就会把0也当合法数字输出组合里就会出现0显然是错的。所以初始startIndex由题目范围决定1到n就传10到n-1就传0。一个简单的判断方法题目要求组合里的数字范围是什么startIndex初始值就是那个范围的最小值。5.3 剪枝边界到底怎么写才不出差一错误剪枝边界的差一错误是所有刷题人都经历过的痛。以77题为例正确定义是循环允许的最大值是n - (k - len(path)) 1。也就是说for循环写成for i in range(startIndex, n - (k - len(path)) 2)因为range是左闭右开要取到最大值得在后面加1。如果你写成 1最后一个合法的起始位置就被漏掉了导致结果少几个组合。我建议每次写完这个边界时手动带一组极端数据验算一遍。比如n4k2第一次进入backtrack时path为空k-len(path)2最大值是4-213。循环从1到3不会选4作为组合的第一个元素。因为选了4以后后面没有数字可选了根本凑不成两个数的组合。这样验算一次就能确认边界没有写错。5.4 216题里current_sum的维护放在哪里216题因为需要记录当前path的和所以多了一个current_sum变量。这个变量的维护必须和path的增删严格同步做选择时path.append(i); current_sum i撤销选择时current_sum - i; path.pop()顺序不能乱。如果你先path.pop()再current_sum - i结果是一样的如果你忘记current_sum - i那么这个值会一直累积后面的递归全部判错——当前和永远大于n结果集为空。我个人的习惯是把current_sum和path紧挨着维护中间不插入任何其他逻辑。等代码跑通以后再考虑是否要把它作为递归参数传递以减少一个全局变量。还有一种写法是把current_sum作为递归函数的参数每次调用时传current_sum i这样就不需要nonlocal声明。两种写法等价但参数传递的方式更干净不用维护撤销时的减操作。不过参数方式的一个小问题是递归参数会多一个看代码时没那么直观。两种方式我都推荐刷题时尝试一遍选自己更不容易出错的就行。5.5 递归深度和性能问题什么时候回溯的复杂度是真扛不住回溯算法的时间复杂度天然是指数级的这是它最大的弱点。在力扣上刷题时n的取值范围一般都不大比如77题的n≤20216题的搜索范围才9所以可以直接用回溯。但如果你在笔试或实际项目中遇到n比较大的情况就要考虑以下几点第一组合数C(n,k)本身会很大。n20k10时组合数是184756回溯可以处理n30k15时组合数超过1.55亿即使有剪枝也大概率超时。第二剪枝能剪掉一部分分支但改变不了最坏情况的复杂度。如果数据设计成所有组合都合法剪枝等于白搭该超时还是超时。第三遇到这种情况考虑换算法思路。比如动态规划、数位DP、组合数学公式推导等看题目是否允许非枚举解法。说实话大部分回溯题能通过剪枝在力扣限定数据范围内跑过但面试时如果答完回溯主动补一句“这个解法在n特别大的时候会超时可以考虑用组合数学优化”绝对是加分项。6. 刷题感悟与建议这两道题怎么刷收益最大把77和216放在同一天刷我是有刻意安排的。这两道题就是一对“教科书CP”放在一起对比着做比单独刷十道零散题目都有用。我的建议是这样操作先不看任何题解第一遍用普通回溯框架把77题写出来画递归树理解每个节点做了什么然后看剪枝版本推导循环上界的数学公式接着去刷216题你会发现自己可以很自然地套用77的框架再加上对current_sum的剪枝。整个过程大概两到三个小时但收获是质的飞跃——之后你在其他回溯题里看到的if 条件: return都会第一时间反应过来“这是剪枝”。另外刷题打卡不要只是写完提交通过就完事。我习惯每道题做完之后在笔记里记录三件事这道题的递归树长什么样、剪枝条件为什么成立、我写代码时卡在了哪一步。这样做的好处是两周之后回头复习不用重新推导一眼就能回忆起整个思路。最后分享一个我调试递归的小技巧在递归函数开头加一行print(fstartIndex{startIndex}, path{path})看一眼输出整个执行流程就全明白了。每次踩坑之后这个小技巧都能帮我快速定位问题。这两道题刷完你对回溯的理解一定会有一个质变。后续不管你往哪个方向深入这个基础都会让你走得更稳。