经常有朋友问我一个零基础的人学算法到底是怎么坚持下来的。说实话我自己也没想到能一路记到第37天。这个系列标题叫“更弱智的算法学习”其实是自嘲——我用最笨的思路去啃那些看起来很高深的概念强行让自己理解而不是背模板。今天要聊的主题是回溯算法一个听起来玄乎、实际却很朴素的算法思想。它特别适合那些一看到“深度优先搜索”、“递归”、“剪枝”就头大的朋友因为只要你能理解“试错”和“回头”回溯的基本骨架就通了。这篇笔记适合正在刷LeetCode、备战蓝桥杯或者准备算法面试的人参考我尽量把每一步为什么要这样做讲明白而不是丢一段代码让你自己悟。1. 为什么第37天还在学“弱智算法”回溯算法的设计思路与适用场景回溯算法本质上就是暴力枚举的升级版。暴力枚举大家都懂把所有可能性列一遍符合条件的留下。回溯在此基础上加了一个“后悔”机制走一步发现不对退回上一步换条路走。这个机制让原本只能硬算的很多问题变成了一种有结构、有章法的搜索。1.1 回溯到底在干什么用一个生活化的类比来感受一下。想象你在整理一个行李箱箱子里要放几种物品每种物品可以放或者不放但箱子容量有限。最笨的方法是把所有放与不放的组合都试一遍看哪个组合最合适。这就是暴力枚举。回溯则在尝试过程中加了一步当你试着把一件外套放进去之后发现剩下的空间无论如何都装不下其他必需物品你会把外套拿出来换一件薄一些的衣服再试。这个“拿出来换一件再试”的动作就是回溯里的“状态重置”。同样的道理排列、组合、子集、数独、八皇后这类问题都符合“多个决策叠加、前一步影响后一步”的结构。回溯做的就是把这些决策过程组织成一棵树从根节点开始向下尝试到叶子节点判断结果不行就回到上一个分支结点重新尝试。这种“一棵树一条路走到黑不行就退回来走另一条”的思路其实就是深度优先搜索DFS。1.2 从暴力枚举到回溯的差距在哪里很多人会问暴力枚举和回溯的代码看起来差不多为什么非要用回溯我给你一个直观的对比数据。假设要生成n个元素的全排列。暴力枚举的思路是“列出所有可能的排列再筛选”但“列出所有排列”本身就要n!种情况没有任何先验信息可以跳过中间步骤。回溯的思路是“在构建排列的过程中只要发现某个位置已经被占用马上放弃这条分支”虽然最坏时间复杂度也是O(n!)但实际运行时无效分支会被大量剪掉尤其是加上剪枝条件之后运行效率完全不是一个量级。此外暴力枚举往往需要自己维护一个“所有状态”的集合内存开销很大。回溯通常只维护一条路径上的状态空间复杂度是O(n)这一点在处理大规模输入时非常重要。我在第30天左右学动态规划的时候最大的感受是“题目太难识别”——你得先判断这题能不能用DP、状态怎么定义、转移方程怎么推。回溯算法在这方面友好很多识别起来很容易只要题目要求你枚举所有组合/排列/方案并且在选择时有约束条件基本就能往回溯上想了。识别门槛低了你才能把精力集中在“剪枝”和“去重”这两件真正考验细节的事情上。2. 回溯算法的核心细节递归结构、状态记录与剪枝回溯算法的代码骨架非常固定核心就三件事选择、进入下一层、撤销选择。这三件事对应到递归函数里分别是在for循环中尝试每个候选值、对候选值进行递归调用、递归返回后把状态改回原样。理解了这三个动作回溯就理解了七成。2.1 递归的骨架选择、进入下一层、撤销用伪代码表示一个标准的回溯函数差不多是下面这个样子def backtrack(路径, 选择列表): if 满足结束条件: 保存结果 return for 选择 in 选择列表: 做选择 # 把当前选择加入路径 backtrack(路径, 选择列表) # 进入下一层决策 撤销选择 # 把当前选择从路径中移除这里最容易被初学者忽略、也最容易踩坑的就是“撤销选择”。好多人写回溯写到最后发现结果全是空的或者结果数量不对十有八九就是忘了撤销选择。我在第29天学递归的时候也犯过这个错误后来自己总结出了一个记忆方法递归函数里凡是修改了传入状态的地方返回之前必须把它改回去。这就好比你去别人家做客坐了人家的椅子离开之前要把椅子推回原位。你不推回去下一个来做客的人可能没椅子坐或者坐在一个歪七扭八的位置上整个搜索空间就乱了。这种“状态共享”正是回溯算法的核心特征。它只用一份变量记录当前路径靠递归的进入和退出天然实现了前进与后退。听起来很精妙但也正是这个特征使得状态污染成为最常见的bug来源。后面我会专门用一个章节来排查这类问题。2.2 剪枝把暴力枚举变成高效搜索的关键如果说递归是回溯的骨架剪枝就是回溯的灵魂。没有剪枝的回溯和暴力枚举没有太大区别有了剪枝回溯才能真正应对规模稍大的数据。剪枝的本质是在进入某条递归分支之前提前判断这条分支是否值得继续。不值得就直接return不再浪费递归调用的开销。剪枝大致分三类。第一类是可行性剪枝意思是当前选择已经不满足题目的硬性约束后面再怎么走都是死路直接砍掉。比如组合总和问题里如果当前路径的和已经超过目标值后面再加任何正数都会超就没必要继续递归了。第二类是最优性剪枝多用于优化问题比如计算最大收益时如果当前收益加上剩余能获取的最大收益都达不到已有最优解这条分支也可以砍掉。第三类是去重剪枝专门针对结果不能重复的情况比如同一层的相同选择跳过或者用visited数组标记已使用的元素。我在实际刷题时发现剪枝条件往往比递归本身难写。因为递归的逻辑是固定的而剪枝需要对题目有足够深刻的理解并且要保证剪枝不砍掉合法解。一个常用的验证方法就是先写一个无剪枝的暴力回溯版本再逐步加上剪枝条件每加一个就对比一次输出结果是否一致。前置条件允许的情况下用几个小规模测试用例跑一遍一旦发现结果少了解说明剪枝条件过猛要放松条件。这个方法虽然笨但能帮你快速定位剪枝条件到底错在哪。第35天我在做一道搜索题时就因为剪枝条件写紧了一位导致结果缺失花了一个多小时才排查出来。3. 实操过程两道经典题目的完整实现与分析单讲概念容易飘还是要有具体的题目撑着。今天我用两道经典题来走一遍完整的回溯流程。一道是全排列一道是组合总和。这两道题分别对应了排列型回溯和组合型回溯搞清楚它们的区别很多同类题你就能举一反三了。3.1 全排列用used数组控制选择范围题目要求是给定一个不含重复数字的数组nums返回所有可能的全排列。比如输入[1,2,3]输出八种排列。这也是最典型的回溯入门题。代码如下def permute(nums): res [] path [] used [False] * len(nums) 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这里有几个细节值得拆开来仔细看。为什么保存结果时要写成res.append(path[:])而不是res.append(path)因为path是一个列表对象后续递归会不断修改它。如果在path上直接append到resres里保存的其实是同一个对象的引用。等递归结束后path被清空res里所有的“结果”也会跟着变成空列表。用path[:]是复制一份当前内容让res里的每个元素成为独立的列表。这个细节我当年至少坑了三次才彻底记住。为什么需要用used数组因为排列问题中每个数字只能被使用一次。如果你在循环里不检查是否被用过就会出现[1,1,1]这样的非法排列。used数组的作用就是标记“这个数字当前已经在path里了”在递归入口处检查并在递归返回后重置。这就是前面说的状态记录与撤销。为什么不用startIndex来控制循环起点排列问题和组合问题的最大区别在于排列中每个位置都可以放任何还没用过的数所以每次递归都要从0开始遍历整个nums而组合问题为了避免重复组合需要用startIndex确保每次只从当前元素之后选择。这个区别对应了used数组和startIndex两种策略的不同使用场景。复杂度方面排列问题的解空间数量是n!每个排列需要O(n)时间来复制结果总时间复杂度O(n×n!)。空间复杂度上res保存所有排列也需要O(n×n!)空间如果只算递归栈和path以及used则是O(n)。在刷题平台提交时必须在脑子里过一遍这两个复杂度确认不会超时或超内存再递交代码。3.2 组合总和剪枝在排序加持下的威力组合总和这道题的设定是给定一个正整数数组candidates和一个目标值target找出candidates中所有“和为target”的组合其中candidates中的每个数字可以被无限重复选取。这道题比全排列多了一个“无限重复”的条件同时要求组合之间不能重复。先上一个最基础的版本不加任何剪枝def combinationSum(candidates, target): res [] path [] def backtrack(startIndex, currentSum): if currentSum target: return if currentSum target: res.append(path[:]) return for i in range(startIndex, len(candidates)): path.append(candidates[i]) backtrack(i, currentSum candidates[i]) path.pop() backtrack(0, 0) return res这个版本有两点要注意。第一backtrack(i, ...)而不是backtrack(i1, ...)因为题目允许同一个数字被重复选取所以在递归下一层时仍然从当前位置开始。第二startIndex的存在保证了组合的有序性比如[2,2,3]和[3,2,2]在搜索过程中只会出现一次因为递归内层的起点始终大于等于外层的位置。但上面的版本在数据规模稍大时会超时。原因很简单如果数组里都是小数字比如[1,2,3]而target是100递归树会膨胀得非常快大量的分支在currentSum已经大于target时才开始返回白白浪费了递归调用。经典的优化方式是先排序然后在递归入口加一个剪枝条件def combinationSum(candidates, target): candidates.sort() res [] path [] def backtrack(startIndex, currentSum): if currentSum target: res.append(path[:]) return for i in range(startIndex, len(candidates)): if currentSum candidates[i] target: break path.append(candidates[i]) backtrack(i, currentSum candidates[i]) path.pop() backtrack(0, 0) return res这里的剪枝条件和前面的版本有一个非常微妙但重要的差别用break而不是continue。因为数组是从小到大排序过的如果currentSum candidates[i]已经大于target了那么candidates[i1]的数值只会更大同样会超过target所以后面所有元素都不用看了直接结束本次for循环。如果这里写成continue虽然也能跳过当前元素但后续更大的元素依然会进来做无用的比较和递归剪枝效果大打折扣。排序是在剪枝之前必须完成的操作。你可以对比一下不排序的版本即使加了剪枝条件也无法保证后续元素一定比当前元素大只能用continue跳过效果就差很多。这一步让我切身体会到为什么“排序 回溯”往往是组合类问题的标配组合。做完基础版之后如果题目要求“candidates中有重复元素且每个元素只能用一次”组合总和II就需要再额外处理去重问题。处理思路是在排序之后for循环内部跳过与前一个元素相同的那个元素并且递归下一层时用i1而不是i。代码如下def combinationSum2(candidates, target): candidates.sort() res [] path [] def backtrack(startIndex, currentSum): if currentSum target: res.append(path[:]) return for i in range(startIndex, len(candidates)): if i startIndex and candidates[i] candidates[i-1]: continue if currentSum candidates[i] target: break path.append(candidates[i]) backtrack(i 1, currentSum candidates[i]) path.pop() backtrack(0, 0) return res这里if i startIndex and candidates[i] candidates[i-1]的作用是在同一层循环中如果当前元素和前一个元素相同说明以当前元素开头的组合已经被前一个元素完整地搜过了直接跳过就能避免重复结果。这里的判断条件是i startIndex而不是i 0因为i startIndex时即使它和前一个元素相等也是本层搜索的合法起点不能跳过。很多人第一次写这个去重条件时用的都是i 0结果把合法答案也过滤掉了这种错误属于典型的“剪枝过猛”。在实际刷题时组合总和II这道题99%的人都会遇到两个问题第一个是重复组合第二个是剪枝把答案剪没了。我的建议是先不要拿大测试用例跑先写一个nums[1,1,2,5,6,7,10]这样的小用例手动推一遍搜索树确认每个分支的去重逻辑都不漏、不错再去跑大用例。4. 常见错误与排查技巧实录这部分算是我这37天整理出来的干货中的干货。回溯算法代码量不大但每个错误都极具隐蔽性可能让你盯着屏幕半天也看不出问题。我把最常见的坑全部列出来再给对应的排查思路。4.1 状态污染忘了撤销的连锁反应这是回溯算法里出现率最高的bug没有之一。症状是结果里出现了各种奇怪的排列或者结果数量爆炸。原因正如前文所说path和used是共享变量你在一层递归改了它们如果没有在返回之前恢复后面的搜索分支看到的就不是初始状态而是上一个分支残留的状态。我排查这类问题的技巧是在递归函数的入口出口各加一条打印语句把当前路径和当前递归深度打印出来然后运行一个小规模的用例。一旦发现某个分支返回之后另一个分支的初始路径里残留了上一个分支的元素问题就基本定位了。经过一两次这样的排查你以后写代码时自然就会先把撤销动作写好习惯成自然。4.2 剪枝条件过紧或过松剪枝条件过紧的症状是结果缺失过松的症状是超时或结果过多。最危险的是“看起来没问题一提交就错”。比如组合总和里剪枝用的是break如果你在未排序的数组上也用break就会导致漏解。反之应该用break的地方用了continue虽然答案对但性能很差当数据量大了就会超时。建议的做法是先把剪枝条件全部注释掉跑一个数据量较小的用例确认基本结果对然后逐步加回剪枝条件每加一个就重跑一次小用例确认结果数量一致最后再用大用例测性能。这个方法看起来繁琐实际很快比盲猜偏健。4.3 排列去重与组合去重的混淆全排列中要求去除重复排列时用used数组结合“如果nums[i] nums[i-1]且used[i-1]没有被使用则跳过”。组合问题中要求去除重复组合时用的是排序加”如果i startIndex且nums[i] nums[i-1]则跳过“。这两个逻辑长得有点像但判定条件完全不同。我见过不少人把这两个条件混用导致排列题输出的结果有重复或缺失。我自己总结的一句话是排列看重用组合看重序。排列问题关注的是位置上的重复占用组合问题关注的是同一层的重复取值。用的时候可以先把这两类模板分开默写再通过题目中的”允许重复“和”顺序是否相关“来决定选用哪个。4.4 结果保存的引用陷阱保存结果时忘记用path[:]或list(path)前面已经详细说过。这一条在写代码时非常容易忽略因为小例子有时碰巧能蒙对——如果递归结束后path恰好还有内容某些错误的结果反而看起来有模有样。最稳妥的办法是养成习惯只要是把path加入结果集一律用切片复制不管当前在写回溯、DFS还是其他递归类问题。这里顺便提一点Python的path[:]是浅拷贝对int、str这类不可变类型完全没有问题。如果路径里放的是可变对象比如列表或字典就必须用深拷贝。不过在回溯题里路径中的元素基本都是数字或字符串这类简单类型少有需要深拷贝的场景。4.5 递归深度与栈溢出回溯是递归实现的递归深度等于解空间的深度。像全排列这类题目递归深度是nn一般不会太大问题不大。但某些题目如果输入数据达到几千递归深度可能超过Python默认的1000层递归限制导致栈溢出。这时候要么用迭代式回溯改写要么增加递归限制。我在练习时很少遇到这种情况但作为常识还是记录下来以防面试时被问到。4.6 常见问题速查表现象常见原因排查方式结果为空或数量比预期少剪枝条件过紧去重条件误伤合法解去掉剪枝跑一次小用例结果数量比预期多忘记去重剪枝条件过松检查同一层是否有重复选择结果中出现重复解组合问题的startIndex用错排列问题used数组忘掉对比题目要求检查递归参数结果全是空列表res.append(path)而非path[:]改用切片复制超时剪枝不足或没用break加入可行性剪枝检查剪枝位置输出的路径顺序诡异状态污染忘记撤销选择递归出口打印路径排查上面这个表格前五条我都在过去一个多月里实际踩过每条都是真金白银的时间换来的教训。5. 从两道题扩展到一类题回溯的变式与适配思路只做完例题不算会我会额外多走一步把回溯题的常见变体梳理一下。很多新题其实就是经典题的元素替换或组合拼接。5.1 排列、组合、子集三个最经典的模板排列、组合、子集这三类问题是所有回溯题的基石。排列用used数组控制元素不重复使用组合用startIndex控制搜索起点避免重复组合子集问题和组合问题的写法几乎一样只是保存结果的时间点不同——子集要在每层递归入口都把当前path加入结果而不是等到满足结束条件时。我每次遇到看似陌生的新题都会先问自己这题是排列型、组合型还是子集型确定了类型模板就搭建了一半。举一个例子幂集问题其实就是“列出所有子集”用子集模板可以直接照搬代码。而LeetCode上的“电话号码的字母组合”则是一个典型的组合型回溯映射关系处理好之后剩下的就是标准的回溯三件套。5.2 棋盘类问题的回溯特色数独、N皇后这类棋盘问题回溯的思想还是一样的但选择列表变成了“每个格子可以填的数字/每个皇后可以放的位置”。这类问题比排列组合更复杂的地方在于合法性检查不是靠简单的used数组或startIndex而是要写一个独立的isValid函数在每次尝试一个位置时进行横、竖、斜方向的冲突检测。我的建议是写完回溯主体之前先把isValid函数单独写好并测试。因为棋盘类问题的isValid往往包含多组条件稍微写漏一个方向就会出现“皇后互相打架”却依然被判合法的情况。把合法性检查独立出来会让你在排错时分清问题到底出在搜索流程还是出在判定函数。5.3 剪枝在不同题目中的具体应用形态除了组合总和中的数值剪枝剪枝还能表现出好几种形态。比如在N皇后问题中已经放过的行、列、对角线都可以作为剪枝条件。在数独问题中当前格子已经填过的数字对应位置的flag数组起到剪枝作用。在单词搜索问题中如果当前字符不匹配就不必继续向这个方向深入这也可以看作一种剪枝。可以说回溯题目的难度差异主要就体现在剪枝策略的优劣上。同样一道题不剪枝的版本可能会超时剪枝合理的版本可以优化到几乎接近线性扫描的速度。这也是为什么我坚持先写出正确版本再逐步优化剪枝——顺序反过来的话你会很难判断到底是剪枝错了还是递归写错了。6. 结合其他算法思维看回溯的边界学了37天我越来越感觉到不同的算法思想之间存在隐含的关联和边界。回溯并不总是一个孤立的选择它跟其他算法之间有不少可以互相切换的接口。6.1 回溯与动态规划的边界有些看似可以用回溯解决的题目实际上用动态规划更合适。一个典型的识别方式是如果题目只要求“判断是否存在”或“计算方案数量/最优值”而不需要精确输出每一种方案那么往往可以用动态规划来降低时间复杂度。回溯会枚举全部方案以组合总和问题为例如果只问有多少种组合方式那么完全可以用DP的背包思路把时间复杂度从指数级优化到O(n×target)。那怎么选我在刷题时的经验是先看输出要求输出所有组合/排列/路径大概率是回溯只输出数量或布尔值先想想DP。还有第二种情况如果回溯的搜索空间非常大而且存在大量重叠子问题即便加了剪枝也会超时这也是考虑DP的另一个信号。第32天学动态规划时我就拿组合总和题目分别用回溯和DP实现了一遍在数据规模小的时候两者结果一致但当target变大时DP的优势非常明显。6.2 回溯与贪心算法的边界贪心算法的特点是“每一步都选当前看起来最优的”不回退。回溯则是“穷举所有可能路径并在必要时回退”。这两者的边界在于贪心不保证全局最优而回溯保证所有解都被遍历到。如果一道题能证明贪心策略的正确性那贪心就是最优选择性能碾压回溯。比如找零钱问题在某些货币体系下贪心就能得到最优解就不需要回溯。但如果货币面额是[3,5,7]而目标金额是10贪心会先选7再选3结果是73貌似刚好但换成[1,4,5]目标金额8贪心会选5111而正确答案其实是44。这种场景就说明贪心不适用要么回溯穷举要么DP求最优。6.3 回溯中的深度优先搜索与广度优先搜索选择回溯本质上是一种深度优先搜索因为它需要一条路径走到黑再回头。但有些问题比如找最短路径用广度优先搜索更合适。广度优先搜到的第一层结果往往就是最短的深度优先则必须把所有可能路径都搜完才能确定最短路。因此在搜索类问题里先判断“需要所有解还是最优解”、“需要词典序还是最短路”再决定用DFS还是BFS。回溯题里绝大多数要求输出所有方案所以DFS是主旋律这没什么好犹豫的。7. 第37天的个人总结与下一步计划学到今天我对回溯的理解已经从“记住模板”进化到了“理解为什么这样设计”。这里的核心体会是回溯是一种带撤销能力的枚举剪枝是把指数级开销拉低的关键而正确的状态管理与去重逻辑决定了解是否合法且不重复。如果让我给刚开始学回溯的朋友一个建议那就是不要急着刷难题先用全排列、组合总和、子集这三道题把三个模板吃透反复手写十遍以上直到不用看模板也能写出来。然后再去碰N皇后、单词搜索这类变体题。下一步我打算把回溯和记忆化搜索结合起来看尤其是在搜索路径上做最优缓存这样可以把一部分回溯算法改造成接近DP的效率。这会是我接下来几天的重点内容。另外刷题时我还发现不少中等难度的题比如分割回文串、复原IP地址、括号生成本质上都是回溯的壳子。把这些题串在一起复习能帮你建立更完整的解题框架而不是孤立地记住一道题。最后分享一个小技巧我在写回溯题时会在纸上先把解空间树画一遍哪怕只是画出前两层。这样做能让递归的入口出口变得异常清晰调试时自然也快很多。第37天学到最重要的不是算法本身而是“敢试错、会回头”的思考方式。