回溯算法从入门到精通：决策树模型、剪枝技巧与经典题型实战

刷题刷到回溯这块的时候很多人会有一种很奇怪的感受代码看着不长逻辑好像也明白但一到自己写就卡壳。尤其是遇到组合、排列、子集、N皇后这些题总觉得差一层窗户纸没捅破。这层窗户纸其实就是没搞明白回溯算法到底在做一件什么事。回溯算法的核心价值在于它把多阶段决策问题变成了一棵可以在脑子里展开的决策树然后用深度优先搜索的方式去遍历这棵树遇到走不通的分支就回头换一条路继续走。这个过程听起来简单真正在代码里落地的时候却藏着不少细节状态怎么维护、选择怎么撤销、哪些分支可以提前砍掉。这篇文章我就把自己这些年写回溯题的一些心得整理出来从模板到实战从剪枝到复杂度一篇聊透。1. 回溯到底在做什么从决策树的角度理解核心机制1.1 为什么回溯能成为通用解题框架先想一个问题给定一个数组让你找出所有长度为 k 的子集你会怎么做。大多数人的第一反应是写多层循环k 是 2 就两层循环k 是 3 就三层循环。但 k 一旦变成一个输入参数循环层数就没法确定了。这时候就得换个思路与其在代码里写死循环层数不如把当前该选哪个元素当成一个决策一步步做下去每一步可选的元素范围由之前的选择决定。这就是回溯算法之所以能成为通用框架的根本原因。它把原来需要动态嵌套层数的循环问题统一转化成递归调用的深度问题——每一层递归对应一次选择递归的深度对应决策的步数而哪些选项可选则是通过函数参数传递的当前状态来约束的。决策树的根节点是初始状态叶子节点是终止状态搜索过程就是从根出发沿着分支遍历所有叶子。拿生活中打比方的话这个过程很像走迷宫。你从一个路口出发遇到岔路就选一条走走到死胡同就退回上一个路口回溯的重点就在这个退换一条从未走过的路继续试。算法里的状态变量就是你在当前路口已经走过的路径记录这个记录不光要知道我走过哪些路还要能在退回来的时候把它恢复原样。1.2 撤销选择这一步为什么不能被省掉撤销操作在回溯里是最容易被新手忽略、也最容易写错的环节。比如求全排列的经典写法里做完一个递归调用之后要把刚才加入路径的元素弹出来把标记数组里的对应状态改回去。这两行代码如果不写程序跑出来的结果会非常诡异——要么路径越加越长要么同一个元素被用了无数次。从原理上解释撤销的本质是恢复调用前的现场。递归函数在返回之后后续代码会继续在同一个循环里尝试下一个选项如果你不把现场恢复成进入这一层递归之前的样子那么下一个选项就会在错误的初始状态上继续做决策决策树就彻底错乱了。这和深度优先搜索里的回溯是同一个概念只有把当前分支对共享状态的影响全部抹掉兄弟分支才能从相同的起点出发。这里有一个我早期踩过的坑直接拿数组的副本去传参也就是每次递归都新建一份数据传给下一层用这种做法来避免撤销。功能上确实能跑对但代价是大量的内存拷贝递归深度一上来就非常慢而且代码很难看。正确做法是维护一份共享的路径和标记进入分支前做修改出分支后撤销修改看起来多写两行但效率和可读性都好得多。2. 一套能通吃大多数题目的回溯代码骨架2.1 模板的三个核心部分路径、选择列表、结束条件回溯算法虽然题目千变万化但基本框架是高度统一的。我习惯把每一个回溯函数拆成三个要素当前已走的路路径、可以继续选的选项选择列表、递归终止的条件通常在叶子节点收集结果。这三者分别对应函数签名里的三个部分模板如下def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 选择列表: 做选择 backtrack(新的路径, 新的选择列表) 撤销选择这个模板看起来简单它的精髓在于做选择和撤销选择这两步夹住递归调用把决策树的每一次前进和后退都完整地表达出来。在很多题的代码实现里选择列表不需要显式地作为一个参数传下去而是通过一个起始索引或者标记数组来间接表示但思维模型上始终是这三要素在流转。2.2 从模板到实战全排列和组合的写法对比光说模板可能还是有点虚我们拿两道最经典的题来对比。全排列要求把所有元素的顺序都打乱组合只要求选出固定数量的元素两者在代码上的差别恰好能体现回溯的两种状态维护方式。先看全排列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再看组合比如求出数组里所有长度为 k 的组合def combine(n, k): res, path [], [] def backtrack(start): if len(path) k: res.append(path[:]) return for i in range(start, n 1): path.append(i) backtrack(i 1) path.pop() backtrack(1) return res区别很明显全排列用 used 数组来防止重复选同一个元素而组合用 start 参数来保证每次只往后选避免出现 [1,2] 和 [2,1] 这种重复组合。这背后是两种不同的决策逻辑——排列关心顺序组合不关心顺序所以组合用只能往后走来天然避免重复这也是为什么组合类的回溯代码里几乎一定能看到 start 参数。2.3 参数设计里最容易埋雷的三个地方回溯函数的参数设计是有套路可循的但恰恰是这里最容易出问题。第一个雷区是不知道哪些信息需要放进函数参数。我的经验是凡是递归过程中需要变化的数据都应该是参数或者共享状态凡是固定不变的数据就定义成外部变量。比如数组本身、目标值这种东西不用传但当前累计和、当前位置、已选数量这类状态必须明确传下去。第二个雷区是使用 list 的引用传递问题。Python 里列表是引用类型直接 res.append(path) 存进去的是一个引用后续对 path 的任何修改都会影响已经存进 res 的结果。必须用 path[:] 做拷贝再 append这是个高频低级错误。第三个雷区是剪切选择列表时边界写错典型的比如 for i in range(start, n) 里面该不该包含 start 本身递归下一层该传 i 还是 i1这些细节依赖于题目说的是可以重复选还是不能重复选。建议把模板固定下来遇到不同题再微调比每次都从零想边界条件要稳得多。3. 三个经典问题的完整推导过程3.1 N皇后问题的逐步思考N皇后是回溯里最经典的问题也是决策树模型最直观的题。它的要求在 n×n 的棋盘上放 n 个皇后任意两个皇后不能在同一行、同一列或者同一条对角线上。这个题我不会一上来就写代码而是先画一棵决策树第 1 行放哪个列第 2 行放哪个列依此类推直到放完 n 行。树的分支就是每一行可选列的范围。代码的关键在于检查一个位置能不能放皇后。正常思路是检查当前列、两条对角线是否已有皇后。常见写法是维护三个集合分别记录已占用的列、行-列差主对角线特征、行列和副对角线特征这样每个位置的合法判断都是 O(1) 的。行-列差为什么能标识主对角线其实只要写两三个坐标算一下就会发现在同一主对角线上所有位置的 行-列 是相等的副对角线同理行列 相等。这个题的剪枝也很天然每一行只有合法位置才会进入下一层递归不合法的列直接跳过。相比全排列N皇后的选择列表天然被棋盘约束削减了这也是回溯题目里非常典型的一类——选择列表不是固定的而是由当前状态动态计算出来的。3.2 组合总和的去重逻辑组合总和系列题目里有个变体给定数组可能包含重复数字要求找出所有和为 target 的组合但组合之间不能出现重复。这题的难点不在搜而在去重。如果不做任何处理直接用标准组合模板搜一遍得到的结果里会出现一模一样的组合比如 [1,2,3] 和 [1,3,2]或者同一个值因为出现在不同位置被判成两个结果。去重的标准做法是先对数组排序然后在同一层递归里跳过值相同的元素。这个同一层是去重的精髓。举个例子数组排序后是 [1,1,2]第一层选了第一个 1 之后进入第二层还可以选第二个 1这是合法的但如果第一层选了第二个 1那么它和选第一个 1 产生的结果是重复的因为前一个分支已经把从一个 1 开始的所有答案搜完了。所以判断条件通常写作 if i start and nums[i] nums[i-1]: continue它保证的是同一层递归的循环里不选重复值但不同层之间依然允许出现相同值。这个细节非常容易写错因为有人会把条件写成 if i 0 and nums[i] nums[i-1]那样就会把不同层之间的合法重复也过滤掉结果丢解。判断条件里的 start 一定要带着它限定的才是当前分支内的去重范围。3.3 分割回文串与隐式回溯有些回溯题的选择列表不是显式的数组而是一个字符串的切割点。比如给定字符串 s要求把它分割成若干个回文子串返回所有可能的分割方案。这个题每一层递归要做的事情是枚举当前剩余字符串的第一个切割点判断前缀是不是回文是的话就从剩余串上切掉这个前缀继续递归处理剩下的部分。这类题我把它叫做隐式回溯因为状态不是一个数组路径而是字符串的剩余长度。同样需要维护一份结果列表每次递归进入时当前已经切出来的回文子串都存在 path 里切到底了就把 path 加入结果集。撤销操作依然是弹出最后一个切出来的子串。做完这道题你会发现回溯不只是在元素间做选择它还能做线段切分之类的选择形态很多但核心的三要素一个没变。4. 剪枝策略回溯题目真正拉开差距的地方4.1 三类高频剪枝的适用场景剪枝是回溯优化的核心思路因为回溯本质上是在遍历一棵完整的决策树如果一棵树规模巨大不做剪枝就会指数级爆炸。常见的剪枝手段大致可以归成三类。第一类是可行性剪枝也可以理解为走不下去就不走了。在组合总和里如果当前已选元素的和已经超过 target那么无论后面再选什么都不可能回到 target这一支可以直接停。N皇后里位置不合法就不进入下一层也是同理。这类剪枝的本质是提前判断当前状态是否已经违反了硬性约束。第二类是去重剪枝主要针对数组里有重复元素的题目用排序加同层跳过的方式来避免搜索重复的分支。这类剪枝前面组合总和部分已经演示过它不改变解的本质只减少无意义的重复搜索。第三类是上下界剪枝常见于组合类题目里可以用来缩小 for 循环的范围。比如在组合题中当前已选了 len(path) 个数还差 k - len(path) 个数才凑满那么循环变量 i 的最大值就不能超过 n - (k - len(path)) 1超过这个位置后面剩余元素就不够填了。这个边界被称为剪枝上限这么处理能让每次递归的遍历范围明显缩小在面对大 n 时性能提升相当明显。4.2 剪枝的顺序对结果和效率的影响剪枝逻辑之间的先后顺序也是有一定讲究的。一个实用的建议是每次进入循环体之前先做条件判断能不进入递归就不进入递归。因为递归函数调用本身是有开销的能在 for 循环外拦截的就别放到递归函数里再去判断。举个例子在组合总和的剪枝中通常会先判断如果当前数字加上已有的总和已经超过 target就要 break 掉整个循环因为数组已排序后面的数字只会更大循环也没必要继续了。但如果是判断当前数字与前一个相同那用的是 continue 而不是 break因为后面可能还有不重复的数。这两种跳出方式的区别在数据规模大时对效率影响很大逻辑上也容易混淆建议你在代码旁边写清楚注释防止过两天回来忘了自己当时为什么这么写。4.3 实测一次剪枝带来的体感变化我曾经拿组合总和 III 这道题做过一个相对不严谨但直观的对比测试题目要求从 1 到 9 中选出 k 个数使其和为 n。不写任何剪枝的时候代码要完整遍历所有从 9 个数里选 k 个的组合在 k 较大时可以感觉到明显的卡顿感。加了两个简单的剪枝之后一是当前和超过 n 直接停止递归二是循环上界按还需选多少个数来动态收缩速度提升可以说是肉眼可见的原先可能要跑很久的测试用例剪枝后几乎瞬间返回结果。这种体验很容易让人上瘾但也要注意一个方向性问题剪枝的本质是减少无效搜索不能以牺牲代码可读性为代价。偶尔看到有人为了剪枝写了一长串条件连自己都解释不清每个条件的来源这种情况下我倾向于保守一点先用清晰的模板跑对结果再逐步加剪枝观察正确性有没有变化。性能优化一定要建立正确性经过验证的基础上。5. 时间空间复杂度与递归深度边界问题5.1 回溯算法的复杂度到底怎么算回溯算法的时间复杂度没有固定的公式可套它取决于决策树的状态数量和每个状态内部的枚举代价。最广泛使用的一种估算方式是把所有可能的状态数量乘上每个状态构造解的平均代价但在实际做题时更常见的做法是看解的个数和每个解的构造代价。比如全排列n 个元素的全排列有 n! 个每个排列的构造代价是 O(n)拷贝路径所以总时间复杂度是 O(n · n!)。组合数是 C(n,k)解的数量就是组合数每个解的构造代价是 O(k)所以总复杂度可以粗略记作 O(k · C(n,k))。N皇后稍微复杂一点解的个数在没有公式的情况下通常用上界 O(n!) 来近似每一层还要做 O(n) 的合法性检查所以粗略算是 O(n · n!)。真正严格的分析还会涉及剪枝对实际分支的影响但对一般面试和交流来说这个量级估算已经足够定位问题了。空间复杂度相对好算一些。递归深度就是决策树的深度也就是递归的最大层数全排列是 O(n)组合是 O(k)再加上路径存储本身的开销通常也在这两个量级之内。除此之外不要把每次递归里的临时变量忽略掉如果递归里存在拷贝大列表的操作那么每一层的栈帧都要承载额外的开销空间复杂度会整体抬高一层。5.2 递归深度和调用栈溢出问题回溯天然依赖递归递归就会受到调用栈深度的限制。Python 默认的递归深度限制是 1000超过之后会抛 RecursionError。回溯题的递归深度一般等于决策步数大多数常规题目深度不会超过几百层问题不大。但如果题目给的 n 很大或者问题本身需要很深的递归就要考虑把递归深度调大比如用 sys.setrecursionlimit(10000)。不过动手调限制之前还是要先想想递归深度特别深的时候是不是算法设计本身就不合理。比如某个问题虽然理论上需要搜 n 步但 n 的值大到上万那么回溯本身就很难在合理时间内跑完真要考虑换策略比如使用迭代形式的 DFS 或者寻找更底层的数学规律单纯扩大递归深度解决不了性能问题。我在实际刷题中见过不少因为栈溢出而卡住的案例排查之后发现根源往往不是深度限制而是终止条件写错导致递归无限延伸这时候去调 setrecursionlimit 就是治标不治本。所以优先检查递归出口的写法再考虑调参。5.3 常见边界问题与错误汇总回溯题目里有一些反复出现的边界问题这里集中梳理一下下次遇到可以逐条对着检查。path[:] 还是 path把 path 加入结果集时如果直接加引用后续 path 一旦变化结果集里的记录也跟着变这是回溯里最常见的错误之一。start 传 i 还是 i1题目允许元素重复选就传 i不允许就传 i1。这个决定不好就会导致解变少或者无限递归。排序操作的位置涉及到去重的组合题排序必须发生在整个回溯开始之前而不是在递归内部。否则去重判断依赖的相邻关系会不稳定。剪枝的 break 与 continuebreak 适用于数组有序且继续遍历后面元素已经无法满足条件的情况continue 适用于只跳过当前冲突元素的情况用混了会导致结果缺解或者多解。递归出口的返回值有些写法里 backtrack 函数有返回值表示是否找到解比如解数独类问题这时要注意返回值的时机找到解之后要及时阻断后续搜索而不是继续跑完整个决策树。6. 回溯算法的实战应用场景与能力边界6.1 从算法题到工程回溯在哪里真实落地回溯不只是一个刷题工具在工程世界里它的身影其实很常见。最典型的是各种约束满足类的场景排课表要满足教师时间不冲突、教室容量够、课程数量匹配任务调度要考虑资源占用和执行顺序游戏里的走迷宫、解数独、猜单词本质上也是回溯搜索。这些问题的共同特征都是多条件约束 求全部或某个可行解暴力枚举不可行但用回溯配合剪枝可以迅速锁定搜索空间里的有效区域。还有一类是编译器和规则引擎里的推导问题比如在语法分析中使用的递归下降算法本质上也是一种带预测和回退的搜索过程。当某个分支解析失败时解析器要回退到之前的某个状态重新选路这和回溯的状态撤销机制如出一辙。理解了回溯的核心思想之后再去读这类源码会明显感觉顺畅。6.2 什么时候不适合用回溯回溯虽然很强大但不是所有搜索问题的最优解。如果一个问题的搜索空间极其巨大而解的分布又极其稀疏那么回溯即便配上剪枝也可能要跑很久。典型例子是某些大规模的最优化问题如果只要求一个最优解而不是所有解那么动态规划或者贪心策略往往更高效因为回溯本质上是穷举只是在穷举基础上去掉一些明显不可能的分支而已。动态规划和回溯的共同点在于都处理多阶段决策不同点在于动态规划会记录子问题的答案避免重复计算。如果一个子问题会被多个上层分支反复触及那么回溯就会在这些重复子问题上白白消耗大量时间这时候用记忆化搜索也就是在回溯基础上加一个备忘录可以保留回溯的思维模型又获得 DP 的复用效果。很多人在刷题时会把记忆化搜索和回溯混在一起其实两者的血缘非常近加上备忘录之后的回溯已经可以和动态规划划上等号了。6.3 如何循序渐进地练习回溯如果你刚开始接触回溯建议按梯队去刷题不要一上来就去啃 N皇后和数独。第一梯队是全排列、组合、子集用来建立模板意识能默写出回溯三板斧。第二梯队是组合总和、分割回文串、括号生成这类在选择列表上做文章的题用来训练对状态空间的理解。第三梯队再上 N皇后、解数独、单词搜索这些题要求你把剪枝和状态维护灵活组合。每写完一道题建议做一次复盘画一下这题的决策树看看每一层的分支是怎么生成的剪枝条件砍掉的是哪些分支撤销操作恢复的是哪些状态。用这种训练方法坚持几十道题以后回溯的很多套路就不需要再想因为在脑子里已经形成了一套自动化的搜索模型了。最后说一个我个人的习惯每道回溯题提交通过之后会再花一两分钟尝试给循环加上各种可行的剪枝再跑一遍之前的测试数据确认结果没有变化。这样做不单是为了优化代码更是为了让自己清楚每一个剪枝条件到底在砍掉什么久而久之面对陌生题目时找剪枝点的直觉会变得相当准。回溯的难点从来不在代码本身而在于有没有建立起搜索一棵树不合适就回头的思维习惯一旦这个模型在脑子里立住了它带来的不只是会做几道题那么简单——你会发现很多看起来很复杂的决策类问题本质上都长着同一副面孔。