回溯算法我愿称之为“暴力美学的极致”。很多人一听到“回溯”两个字就觉得头疼觉得它又抽象又难写什么递归、状态重置、剪枝一堆概念叠在一起。但如果你真正把它拆开看就会发现它本质上就是一个“有策略地穷举”的思维过程你不需要一下子想出什么精妙的数学公式你只需要学会如何把一个大问题拆成一模一样的小问题再学会如何“反悔”。今天这篇day24笔记我就把回溯算法从头到尾、从原理到模板、从经典题到剪枝优化一次说透。很多人分不清回溯和递归的关系其实回溯是基于递归来实现的递归是它的“壳”而回溯是它的“魂”。我们日常写的DFS深度优先搜索本质上就是回溯的一种体现。所以如果你国庆力扣刷题刷到“全排列”“组合总和”“子集”这类问题时感觉卡壳不用怀疑自己的智商绝大多数人都是卡在“为什么撤销这一步”这个坎上。这篇我会先带你搭出回溯的通用模板然后拆解组合、排列、子集、切割、棋盘这几大类高频题型的解法后面再讲剪枝和去重这两个真正决定你能不能AC的关键。全程用大白话配上代码和踩坑记录保证你学完能直接上手写题。1. 回溯算法的本质把“反悔”变成一种搜索策略1.1 从一次“走迷宫”说起想象你在走一个迷宫走到岔路口时你随便选了一条路走结果走到死胡同了。这时候你怎么办是不是退回到上一个岔路口换一条路继续尝试这个“退回去换条路走”的动作就是回溯。计算机里的回溯算法干的就是这件事只不过它不是人肉走迷宫而是通过递归这个机制把每一步的选择和撤退都交给函数调用栈来管理。我们用代码去描述“我选了某个元素”这个状态然后递归去探索后续所有的可能性等这一条路探索完了再把状态改回选之前的样子继续尝试下一种可能性。这个“改回选之前的样子”的操作就是很多人常说的状态重置backtrack。它是回溯的灵魂所在也是最容易被忽略、最容易写错的地方。一旦忘记重置你会惊讶地发现你的结果里出现了各种莫名其妙的重复组合或者路径越攒越长。1.2 回溯算法能解决哪四类问题从刷题的角度来看回溯算法的应用场景非常固定LeetCode上的回溯题几乎逃不出这四类组合问题从N个数中按一定规则选出K个数比如“组合总和”。切割问题一个字符串按一定规则切割成若干子串比如“分割回文串”。子集问题求一个集合的所有子集比如“子集II”。排列问题N个数按一定顺序全排列比如“全排列”。另外还有一类棋盘类问题比如N皇后、解数独本质上也是回溯只是每一层的选择变成了“在棋盘的某个位置放什么棋子”。你可以把棋盘问题理解为“组合/排列问题的空间升级版”。1.3 为什么回溯不是简单的暴力枚举暴力枚举和回溯算法的区别在于暴力枚举会无差别地尝试所有可能哪怕是已经可以判定走不通的情况它也照样递归下去。而回溯算法往往带一个剪枝操作在递归之前判断一下发现这条路已经不可能产生合法结果就直接放弃不再往这个分支投递任何计算。举个例子你要在1到10这10个数里选3个数组成组合并且要求组合的和不能超过5。如果你用纯暴力枚举你会先选出(1,2,3)发现和是6超了然后继续选(1,2,4)又超了……所有组合都要算一遍。但如果用回溯加剪枝一旦发现当前路径的和加上剩下最小的那个数都已经超过5就直接return后面的计算全部省掉。数据量小的题目也许看不出差异数据量一旦上来剪枝与否可能就是超时和秒过的区别。2. 回溯算法的通用模板与核心框架2.1 七行核心框架先背熟我做深度优先搜索类题目做了几百道之后总结出一个现象所有的回溯题代码骨架几乎是一模一样的。把这个模板背熟往里面填逻辑就行。用伪代码写的框架长这样def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择展开成Python代码核心逻辑就是三步result [] def backtrack(path, choices): if 终止条件: result.append(path[:]) # 注意是拷贝不是直接append(path) return for i in range(len(choices)): # 剪枝条件可以放在这里 路径做选择 backtrack(path, 新的choices) 撤销选择 backtrack([], 初始choices)这个模板里最关键的是两个动作“做选择”和“撤销选择”。做选择时我们要把当前元素加入path撤销选择时要把之前加入的元素弹出来。很多刚入门的朋友都会写出类似这样的错误result.append(path) # 错误写法这样写的结果是最后result里面所有元素变成了同一个列表的引用而由于回溯时path会被修改你会发现最终结果是一堆重复的空列表或重复的排列。这里需要特别记住的是要append(path[:])拷贝一份快照。2.2 参数设计哪些东西要在递归函数里传递设计递归函数参数是个技术活。参数太多了代码看起来很笨重参数太少了状态又传不完整。根据我的经验回溯递归函数至少需要这几样东西当前位置或当前层数用来判断递归何时终止。当前路径path记录了到目前为止做了哪些选择。剩余可选项或者可选范围告诉下一层递归还有哪些选择可以做。通常用startIndex或者一个used数组来表示。全局结果集合result用来收集所有满足条件的路径。我强烈建议把result定义为类属性或者全局变量而不是在递归参数里传来传去。因为Python的函数参数传递机制里列表是可变的你传进递归的是引用所以不在参数里传它完全没问题反而能让代码更清爽。2.3 递归终止条件怎么判断终止条件一般分两种。第一种是路径长度达到目标比如组合问题要求选够K个数排列问题要求排列长度等于数组长度这种直接判断len(path)是否等于K即可。第二种是遍历完了所有可选择的位置比如子集问题startIndex已经越界到了数组末尾以后。还有一种稍微特殊的情况是求和类问题比如组合总和当当前路径的和已经大于目标值时即使路径长度还没达到K也可以终止。这一条通常会和剪枝混在一起但它本质上也是终止条件的一种表现形式。3. 经典题型拆解组合、子集、排列的三角关系3.1 组合问题startIndex控制的是“不回头”组合问题是回溯里最基础、最核心的题型。它的特点是顺序不重要也就是(1,2)和(2,1)算同一种结果。所以我们需要用一个startIndex来确保递归下一层时只能从当前位置的后面的元素开始选这样就不会产生逆序组合。看一道非常标准的题目LeetCode 77 组合。给定n和k返回1到n中所有可能的k个数的组合。def combine(self, n: int, k: int) - List[List[int]]: result [] path [] def backtrack(start): if len(path) k: result.append(path[:]) return for i in range(start, n 1): path.append(i) backtrack(i 1) path.pop() backtrack(1) return result这段代码里只有一个精妙之处backtrack(i 1)。它保证了下一层递归的起始位置在i的后面这样就天然避免了重复组合。如果你写成了backtrack(start 1)那(1,3)和(3,1)就会被算作两种不同的组合结果必然出错。3.2 子集问题每次递归前都要记录当前状态子集和组合非常相似区别只在于组合的终止条件是长度达到K而子集则是每进入一层递归就要把当前路径加入结果集。因为空集是子集长度为1的集合也是子集长度为2的也是子集所有中间状态都是最终结果的一部分。看看LeetCode 78 子集的写法def subsets(self, nums: List[int]) - List[List[int]]: result [] path [] def backtrack(start): result.append(path[:]) # 每一层的path都是一个子集 for i in range(start, len(nums)): path.append(nums[i]) backtrack(i 1) path.pop() backtrack(0) return result注意我把result.append(path[:])放在了for循环外面这样保证进入某个节点时就先收集当前路径然后再去遍历下一层的所有分支。如果你把它放在for循环里面就会漏掉空集和每一层的前缀子集。有个时候我看到有人把子集问题写成先按子集长度分组每次调用一个不同长度的组合解法也不是不行但效率上完全没有必要。一次回溯就能把从0到N长度的子集全部收集齐何苦写N遍循环呢3.3 排列问题used数组而不是startIndex排列问题和组合问题最大的区别在于排列里(1,2)和(2,1)是两个不同的答案。所以startIndex这套“不能回头”的策略就行不通了你得允许每一层递归都能从头开始选。但这样又会出现新的问题比如选了1之后下一层还是可以选1这就产生了重复排列。所以排列问题的核心是维护一个used数组用来标记哪些元素已经被用过。每一层的for循环遍历的是整个数组但是只跳过那些已经被用过的元素。LeetCode 46 全排列的标准解法def permute(self, nums: List[int]) - List[List[int]]: result [] path [] used [False] * len(nums) def backtrack(): if len(path) len(nums): result.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 result这段代码是我觉得全排列里最经典的写法。used数组在进入递归前标记为True递归结束后恢复为False这个True和False的反复横跳就是“状态重置”最直观的体现。全排列题目看着花样多实际上只要把used的标记和撤销写对了剩下的都是体力活。3.4 组合总和与剪枝的第一次相遇到组合总和这道题回溯开始展现出真正的威力。LeetCode 39 组合总和给一个无重复元素的数组candidates和一个目标数target找出所有可以使数字和为目标数的组合。candidates中的数字可以被无限重复选取。这里和之前组合问题的区别是同一元素可以重复使用。所以我们的递归下一层不能再从i1开始而要从i开始。但为了不产生(2,3)和(3,2)这种重复组合还是要保留startIndex来控制方向。标准的写法是这样def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: result [] path [] def backtrack(start, current_sum): if current_sum target: return if current_sum target: result.append(path[:]) return for i in range(start, len(candidates)): path.append(candidates[i]) backtrack(i, current_sum candidates[i]) path.pop() candidates.sort() backtrack(0, 0) return result这里有一个非常实用的剪枝点先把candidates排序。排序之后当for循环里某个元素加上当前和已经超过target那后面的所有元素也一定会超过target直接break。这样比递归进去再判断快很多。有的资料会把剪枝条件写进递归函数开头就是current_sum target就return。这个逻辑没错但效率不如在for循环里提前判断。我实测在数据量大的情况下提前剪枝至少省掉一半的无效递归调用。4. 去重实践为什么你已经回溯却还是一堆重复答案4.1 用排序加相邻元素比较实现横向去重如果要给回溯算法找一个最容易出错的考点去重绝对排第一。很多同学在写“组合总和II”和“全排列II”时明明用了used数组也用了startIndex但结果还是会出现重复的组合或排列。这里引入两个概念树枝去重和树层去重。举个例子假设输入是[1,1,2]在递归的同一层for循环里第一个1会生成一系列结果然后第二个1又会在同一层重新生成这一系列结果这就是“树层重复”需要去重。而如果是在同一个分支里连续选了两个1那是“树枝重复”这种一般是允许的。实现树层去重的标准姿势是先把数组排序然后在for循环里判断当前元素是否和前一个元素相同并且前一个元素的used状态是False。以LeetCode 40 组合总和II为例def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]: candidates.sort() result [] path [] used [False] * len(candidates) def backtrack(start, current_sum): if current_sum target: result.append(path[:]) return for i in range(start, len(candidates)): if i 0 and candidates[i] candidates[i-1] and not used[i-1]: continue if current_sum candidates[i] target: break used[i] True path.append(candidates[i]) backtrack(i 1, current_sum candidates[i]) path.pop() used[i] False backtrack(0, 0) return result这个used[i-1]的判断是比较难理解的我解释一下在同一个for循环即同一层里如果前一个相同的元素已经被回溯恢复了也就是used[i-1]为False说明它已经把以它为开头的那条路径全部探索完了那后面的这个相同元素继续探索就一定是重复结果所以跳过。但如果used[i-1]是True说明当前正在同一个递归分支里前面那个相同元素是父节点那这第二个相同元素属于树枝上的合法使用不能跳过。4.2 用used数组处理集合的去重问题全排列的去重和组合的去重有一点点区别因为排列没有startIndex每一层都会遍历整个数组。所以去重条件里除了判断前一个相同元素没被使用之外还要额外判断当前元素本身是否已经用过。LeetCode 47 全排列II的标准写法def permuteUnique(self, nums: List[int]) - List[List[int]]: nums.sort() result [] path [] used [False] * len(nums) def backtrack(): if len(path) len(nums): result.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]) backtrack() path.pop() used[i] False backtrack() return result这套组合拳打下来你基本就把去重问题搞定了。但说实话我当年学到这里的时候这个“not used[i-1]”也是看了很多遍才真正理解建议你如果第一遍看不懂直接拿[1,1,2]这个小例子手动画一下递归树把每一步used数组的状态写下来马上就能豁然开朗。4.3 不用used数组的去重方法startIndex流派其实还有一个去重流派完全不用used数组而是借助set来实时记录本层已经使用过的元素。思路是在每一层递归内建一个set如果当前元素已经在本层出现过就直接跳过。这个写法在组合总和II里尤其简洁def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]: candidates.sort() result [] path [] def backtrack(start, current_sum): if current_sum target: result.append(path[:]) return used_in_level set() for i in range(start, len(candidates)): if current_sum candidates[i] target: break if candidates[i] in used_in_level: continue used_in_level.add(candidates[i]) path.append(candidates[i]) backtrack(i 1, current_sum candidates[i]) path.pop() backtrack(0, 0) return result这种做法的优点是逻辑简单不需要去理解used[i-1]和used[i]的关系缺点是要额外开辟set。在数据量很小的时候完全没问题数据量大的时候排序加used数组的组合通常更稳。我的写法偏好是排列去重用used数组组合去重用used数组每层set法作为辅助理解。5. 剪枝优化从会做题到高效AC的分水岭5.1 组合问题的经典剪枝剩余元素不够了就直接停组合问题的剪枝公式是一个在网上流传很广的公式很多教程里都有但讲清楚为什么的人不多。还是以LeetCode 77为例题目要求从n个数里选k个。我们已经选了path长度个元素还需要再选k - len(path)个。在for循环里遍历到某个i时如果i之后剩余的元素个数已经不够补齐所需数量那以i为开头的所有分支都注定无法凑齐k个数可以直接break。具体代码这样写for i in range(start, n 1): if n - i 1 k - len(path): break path.append(i) backtrack(i 1) path.pop()这个剪枝在n20、k19这种极限数据下效益极其明显。如果不剪枝前几层几乎要把所有组合都遍历一遍剪枝后很多分支在第一层就断掉了。5.2 求和问题的剪枝排序加提前break求和类问题组合总和、组合总和II的剪枝核心是排序。只有先排序才能保证数组的单调性从而利用“当前元素太大后面元素更大直接break”这个逻辑。剪枝要放在for循环里不要放在递归入口因为递归入口的剪枝只是“死亡后拦截”for循环里的剪枝是“过河前拆桥”。前者省的是递归函数内部继续执行的指令后者省的是整个递归分支全套调用链的产生。你可能会问那求和等于target的时候递归函数开头的current_sum target判断还要不要答案是要但它是安全性兜底而不是性能优化。因为在for循环里你已经保证current_sum candidates[i]不会超过target正常逻辑下递归进去的current_sum都不会大于target但出现一些特殊情况时兜底判断能防止死循环。5.3 棋盘问题的剪枝思路N皇后这类棋盘问题是回溯里思想最巧妙的。每一行只放一个皇后所以递归层数就是棋盘行数每一层的for循环遍历的是列的位置。剪枝发生在放置皇后前的合法性校验需要检查同列、两条对角线上是否已经有皇后。很多初学者会用一个二维数组来记录棋盘上的皇后位置校验时遍历整个棋盘这种写法的复杂度很高。提供一个常用优化用三个数组分别记录“列是否被占用”“主对角线是否被占用”“副对角线是否被占用”因为主对角线的行列是定值副对角线的行-列是定值用索引直接O(1)查询。def solveNQueens(self, n: int) - List[List[str]]: result [] board [. * n for _ in range(n)] col_used [False] * n diag1_used [False] * (2 * n - 1) diag2_used [False] * (2 * n - 1) def backtrack(row): if row n: result.append(board[:]) return for col in range(n): diag1 row col diag2 row - col n - 1 if col_used[col] or diag1_used[diag1] or diag2_used[diag2]: continue col_used[col] True diag1_used[diag1] True diag2_used[diag2] True board[row] . * col Q . * (n - col - 1) backtrack(row 1) col_used[col] False diag1_used[diag1] False diag2_used[diag2] False backtrack(0) return result严格来说这叫可行性剪枝是回溯题里最基础也最必要的剪枝。N皇后如果不用任何剪枝全排列式的探索会把每种摆法都试一遍复杂度直接爆炸。6. 回溯算法的时间复杂度与性能分析6.1 普通回溯的复杂度估算方法回溯的时间复杂度通常不是简单的O(N)或者O(N²)而是和递归树的节点数直接相关。你画一棵递归树每个节点代表一次递归调用树的整体节点数乘以每个节点内部的操作成本就是回溯的总时间复杂度。拿全排列来说第一层有N个选择第二层每个节点有N-1个选择第三层N-2个选择最后一共有N!条叶子路径。所以全排列的时间复杂度是O(N!)空间复杂度是O(N)。组合问题则复杂一些每个节点的分支数不断递减总结果数是C(n,k)整体复杂度可以记为O(C(n,k) * k)。6.2 剪枝对复杂度的影响剪枝能优化常数但一般不改变算法的渐进复杂度阶数。什么意思就是剪枝后仍然是O(N!)级别的复杂度但实际的运行时间可能从10秒降到0.5秒这是数量级的体验差异在面试笔试里这决定你能不能AC。所以我的建议是不要指望通过剪枝把回溯算法从“不可用”变成“可用”回溯天生适合数据规模很小的场景。在真正的算法比赛中N大于20你就要考虑是否需要换用动态规划或贪心而不是硬着头皮写回溯。6.3 动态规划与回溯怎么选回溯和动态规划有交集尤其是“组合总和”这种题既可以用回溯解也可以用DP解。区别在于回溯求的是“所有具体方案”DP求的是“方案数”或“最优值”。如果你的题目要求输出所有解那就只能回溯如果只求个数、只求能不能那就优先考虑DP因为DP有重叠子问题的优化而回溯没有。划重点看到“所有组合”“所有方案”“所有路径”这三个字首选回溯看到“多少种”“最大值”“最小值”“是否存在”先想DP或者贪心。7. 刷题路径推荐与实战心法7.1 按顺序刷完这十道题回溯基本就通了我结合自己的刷题经验给你排一个最适合入门的刷题顺序每道题都有它独特的技术点一题一关打完这些关卡你的回溯水平会有一个质的提升。LeetCode 77 组合学startIndex这是回溯的基石。LeetCode 216 组合总和III组合加求和剪枝的综合练习。LeetCode 17 电话号码的字母组合把回溯用在映射问题上锻炼把真实问题建模成组合选择。LeetCode 39 组合总和允许无限重复取同一个元素学i和i1的区别。LeetCode 40 组合总和II去重入门一定要吃透used[i-1]那个判断。LeetCode 78 子集体会“进入节点就收集结果”的思路。LeetCode 90 子集II子集加去重巩固树层去重。LeetCode 46 全排列从startIndex切换到used数组体会两种控制方式的不同。LeetCode 47 全排列II去重高阶排列和去重的双重结合。LeetCode 131 分割回文串切割问题其实也是组合问题但需要你做回文判断剪枝。LeetCode 51 N皇后最后的综合大boss把二维选择和剪枝玩明白。这道题列表覆盖了组合、排列、子集、切割、棋盘五大题型每一道做完之后试着不参考任何答案自己重新写一遍完整的AC代码隔一天再写一遍直到能默写为止。7.2 实战中的几个致命细节这部分是纯经验分享我踩过的坑不想你在同一处再摔一次。第一个坑是result.append(path[:]) vs result.append(path)。前面提过但这里再强调一次。因为Python的列表是引用传递不拷贝的话result里所有元素都指向同一个path对象最终回溯结束path变成空列表result就是N个空列表。解决办法只有一句永远是path[:]。第二个坑是递归函数参数里的list做默认值。比如def backtrack(path[])这个写法在Python里是一个经典陷阱因为默认参数在函数定义时就创建并共享所有递归分支操作的都是同一个列表。至于结果有多惨你自己试试就会印象深刻。第三个坑是忘记把used[i]恢复为False。一旦忘记第一层递归用掉的元素在另一条分支里也被当成用过直接导致结果少了一大堆排列。每次写完回溯养成自检习惯看看“做选择”和“撤销选择”是否成对出现。第四个坑是在for循环里修改path时不小心用了remove而不是pop。回溯撤销选择时一定要弹出末尾元素也就是pop()而不是按值删除某个元素。按值删除在存在重复元素时会删错对象逻辑会彻底混乱。7.3 针对新手学习路线的心法建议回溯算法的学习曲线确实有些陡峭但它一旦过了那道坎之后就全是套路。我辅导过不少刚开始学算法的朋友发现他们最容易卡住的地方不是不知道怎么写回溯而是不知道什么时候该用回溯、什么时候该用DP。给你一个非常粗暴但有效的判断法题目里的数据范围n小于等于15到20左右并且要求列出所有符合条件的方案那大概率是回溯。因为20!已经是一个天文数字但剪枝后的回溯勉强可以跑出结果而如果n已经到了100、1000还要列所有方案那你得想想是不是题意理解错了可能只是让你输出方案数这时候回溯就不合适了。另外学回溯时一定要亲手画递归树不要只在脑子里想象。画递归树的目的不是为了让别人看懂而是让你自己能直观地看到“什么时候产生了重复”“剪枝应该落在哪一层”。我当年学全排列II的时候手动画了满三层的递归树用红笔圈出所有重复分支写完这个之后之后所有去重题我都没再出过错。8. 总结的经验如何彻底吃透回溯算法的套路与变形回溯的一大特点是变着花样出题但剥开外壳里子永远是那三块递归、选择、撤销。今天我把组合、排列、子集、切割、棋盘五类问题全部归类了一遍你会发现它们的解法代码长得几乎一样区别只在startIndex、used数组、去重条件、终止条件这几处参数上。如果你现在已经能独立写出组合和全排列这两道题恭喜你回溯已经算入门了。接下来要做的不是盲目刷更多的新题而是把做过的题目多做几遍用不同的写法比如把used数组改成set或者把递归改成迭代去重写同一道题体会不同写法之间的等价关系和性能差异。还有一个小习惯我留着最后说每次刷回溯题时都会在代码注释里写出对应题目的“递归树结构”和“状态变量含义”。等注释写多了你会发现自己看一眼题目就知道该定义哪些变量了这种直觉才是刷题真正的核心竞争力。回溯可以难也可以很简单区别只在于你是否真正理解了那一次次的“反悔”。