第一次接触回溯法的时候我也觉得这东西有点玄明明是递归为什么每次做完要把状态“改回去”直到亲手写了几道排列和组合的题才明白回溯法其实就是一套有纪律的试错流程——走不通就退一步换条路继续试直到把所有候选路径走完。它解决的是“在众多选项中找出所有满足约束的解”这一类问题也是入门算法绕不开的必修课。这篇内容会先讲清楚回溯法背后那棵决策树给出一套能直接套用的递归模板再用全排列和组合总和两个经典例子把实现细节翻出来看一遍。适合刚开始学算法、准备面试、或者对递归和搜索始终“感觉会但写不顺”的开发者。看完之后你至少能判断一个问题该不该用回溯并且能独立写出带剪枝的求解代码。1. 回溯法的核心思想先有“一棵决策树”再有递归函数1.1 状态空间树所有答案都挂在树上很多讲回溯的资料上来就扔递归代码结果读者连循环为什么这样写都不明白。我建议换个角度先别管代码把问题想象成一棵树。以“从{1,2,3}中选出2个数”为例。第一个位置可以选1、2、3这是树的三个一级分支。选了1之后第二个位置只能在{2,3}里选选了2之后第二个位置只能在{1,3}里选。每一层都对应“下一个位置的选择”每一条从根到叶子的路径都对应一个候选答案。回溯法做的事情本质上就是深度优先地遍历这棵树。遍历的过程中会走到叶子——也就是完整解也会走到“这条路已经不可能满足条件”的节点——此时不再往下走直接返回上一层换一条分支这一步操作就是“剪枝”。为什么一定要树形思考因为树形思考能强制你回答三个问题每一层递归在决定什么当前已经做出的选择用什么记录还有哪些选择是可用的这三个问题想清楚递归函数的参数基本就定下来了。我见过太多人直接照抄模板抄到“看起来像回溯但又不对”就是因为没有把决策树画出来导致参数传递一团乱。1.2 为什么需要“撤销选择”退回一步才能换条路回溯的英文backtrack直译就是“后退轨迹”。“前进”靠递归调用“后退”靠函数返回但函数返回并不会自动帮你改数据。如果你在进入分支前往路径数组里加了一个元素返回时却忘记删掉它那么下一层分支看到的路径就已经被上一个分支污染了。用一个迷宫类比就很好理解你走到死胡同要回到上一个岔路口这时候不光脚步要退回去你手里的记号也得退回去——不然下一个岔路你拿着错误的行进记录做判断肯定会走错。代码层面最典型的模式就是path.append(choice) # 做选择 backtrack(path, ...) # 往前探索 path.pop() # 撤销选择恢复现场这里的pop和append是严格成对出现的。我在实际写代码时养成了一个习惯把“做选择”和“撤销选择”看成一对括号写完append立刻检查有没有配套的pop写成对称结构后递归基本不会出现状态污染。1.3 哪些类型的问题天生适合回溯不是所有搜索问题都适合回溯但有一类问题几乎是回溯的专属领地要求枚举所有可能解且当前选择会影响后续选择集合的场景。问题类型典型问题为什么适合回溯排列类全排列、字符串排列每个位置的选择会改变剩余可选集合组合类组合总和、从数组选k个数需要按顺序枚举避免重复子集类求所有子集、子集去重每个元素有“选/不选”两条分支搜索类单词搜索、矩阵中找路径路径探索需要记录访问状态棋盘类N皇后、数独放置和撤回天然匹配“状态还原”构造类括号生成、分割回文串在构造过程中判断合法性这些问题的共同特征就是解空间是巨大的但可以用递归一层层收缩选择范围同时每一步决策之间是强相关的不能单纯用几层for循环嵌套硬写。回溯让“枚举”这件事变得结构化比手写多层循环清晰得多。2. 一个模板走天下回溯递归的通用骨架2.1 四行核心结构建议直接背下来回溯的代码模板高度统一几乎所有题都跑不出这个框架def backtrack(路径, 可选列表): if 满足结束条件: 记录结果 return for 选择 in 可选列表: 做选择 backtrack(新路径, 更新后的可选列表) 撤销选择四个部分各司其职结束条件一般是“路径长度达到要求”或者“当前累积值满足目标”。一旦满足就用当前路径生成一个解。for选择遍历当前层还能考虑的所有选项。做选择把当前选项加入路径同时更新约束状态比如标记某个元素已使用。撤销选择把刚才加入路径的元素移除把状态改回去保证同一层的其他分支从同一个起点出发。这个模板难点不在于背而在于“可选列表”怎么随着递归一层层传下去。很多新手把可选列表传成了原数组本身结果递归层数深了之后出现重复选择甚至死循环。举个例子求全排列时第二层递归的可选列表就不再包括第一层已经选过的数字。你当然可以在每次递归时用列表推导重新生成剩余元素但更高效的做法是维护一个used数组标记每个下标是否被用过。used数组在这里本质上就是“可选列表”的状态化表示。2.2 选择列表的更新方式三种常见写法对比我整理了三种最常用的“可选列表维护”方案各有适用场景写法核心思路适用场景注意点used数组用布尔数组标记元素是否已选排列类、需要区分同值不同位置的问题撤销时要把标记改回Falsestart索引下一层从当前下标之后开始选组合类、子集类注意是传i还是i1集合减法每层递归用list comprehension生成剩余集合思路直观的入门写法频繁创建新列表效率低初学者最容易搞混的是传i还是传i1。传i1表示每个元素只能选一次适合组合总和II里“不允许重复使用同一元素”的场景传i表示当前元素可以继续被后续层选中适合组合总和I里“同一个数可以重复选择”的场景。一个字母之差含义完全不同。我建议把这三套写法都在纸上推一遍每个写法对应两三道题形成条件反射。这样写代码的时候不需要在脑子里临时推导准确率会高很多。2.3 剪枝让回溯从“暴力”变“聪明”回溯不加剪枝就是纯暴力枚举加了剪枝才能实际跑过数据量稍大的用例。所谓剪枝就是在递归深入之前判断“当前这条路已经不可能产生合法解”直接return把这棵子树整个跳过。剪枝的位置通常放在for循环里进入递归之前。常见套路是如果当前累计值已经超过目标值直接跳过后续选项。如果数组预先排序当前元素已经过大那么后续元素只会更大可以提前终止循环。如果相邻分支会产生重复解先判断再跳过。剪枝三条经验剪枝条件必须“不会误伤合法解”。宁可少剪不可错剪。先排序再剪枝往往效果翻倍尤其针对组合类问题。剪枝不只为了性能也是去重的重要组成部分。有一条很容易犯的错误排序后判断sum nums[i] target有人写成了continue有人写成了break。如果不排序两者都能用但排序之后continue仍然会遍历后面更大的数字不痛不痒break才能真正利用有序性提前退出整个循环。这两种写法的时间差距在数据量大时非常明显。3. 实操拿全排列打底拿组合总和练剪枝3.1 全排列第一题不写对状态还原后面全乱全排列是回溯的入门必修题。题目很简单给定一个不含重复数字的数组返回所有可能的全排列比如输入[1,2,3]输出包含[1,2,3]、[1,3,2]等六种排列。第一版代码我推荐写成这样def permute(nums): res [] n len(nums) used [False] * n def backtrack(path, used): # 结束条件路径长度已经等于数组长度 if len(path) n: res.append(path[:]) # 注意是path[:]而不是path return for i in range(n): if used[i]: continue # 做选择 used[i] True path.append(nums[i]) # 递归探索下一层 backtrack(path, used) # 撤销选择 path.pop() used[i] False backtrack([], used) return res为什么res.append(path[:])要加[:]因为path后续还会被修改直接appendpath只是把同一个引用存进结果列表。等到回溯函数返回path被pop回空数组所有存进去的“结果”也跟着全变成空数组了。这就是经典的拷贝陷阱后面会细说。全排列的时间复杂度是O(n!)因为第一层n个分支第二层n-1个分支总叶子数就是n!。这个复杂度决定了它只能处理n比较小的情况一般n超过10就要考虑换思路了。3.2 组合总和I排序加剪枝省掉一多半无效计算组合总和I的题意为给定一个无重复元素的数组candidates和一个目标数target找出所有可以使数字和等于target的组合。candidates中的数字可以无限制重复被选取。先排序然后搜索的时候如果当前和已经超过target就提前终止。完整代码def combinationSum(candidates, target): res [] n len(candidates) candidates.sort() # 为了让剪枝生效 def backtrack(start, path, cur_sum): if cur_sum target: res.append(path[:]) return for i in range(start, n): # 剪枝排序后的数组后面的元素只会更大 if cur_sum candidates[i] target: break path.append(candidates[i]) # 允许重复使用当前元素所以下一层仍然传i backtrack(i, path, cur_sum candidates[i]) path.pop() backtrack(0, [], 0) return res注意这里传递的是i而不是i1。因为题目允许同一个数字重复选取所以下一层仍然可以从当前下标开始。如果你写成i1就变成了每个数字最多选一次恰好对应另一道题——组合总和II。排序在这里发挥着关键作用排序后数组从小到大排列一旦某个值加上当前累计和超过target后面所有值只会更大必然也超过target此时直接break退出整个循环。如果不排序就只能一个个continue跳过无法提前终止整轮循环。3.3 组合总和II去重关键在“同一层跳过相同的数字”组合总和II多了一个限制原始数组可能包含重复数字但每个数字在每个组合中只能使用一次且结果中不能出现重复组合。先看代码def combinationSum2(candidates, target): res [] n len(candidates) candidates.sort() # 排序是去重的基础 def backtrack(start, path, cur_sum): if cur_sum target: res.append(path[:]) return for i in range(start, n): # 同一层跳过相同数字避免产生重复组合 if i start and candidates[i] candidates[i - 1]: continue if cur_sum candidates[i] target: break path.append(candidates[i]) # 每个数字只能用一次所以下一轮从i1开始 backtrack(i 1, path, cur_sum candidates[i]) path.pop() backtrack(0, [], 0) return res去重条件i start and candidates[i] candidates[i-1]的理解很关键。它只在“同一层递归的for循环”中跳过重复值。也就是说如果第一个数字选了第一个1进入分支探索第二轮循环遇到第二个1发现和前一个1相同跳过。为什么不直接判断i 0因为i 0会把“不同层之间”的重复也拦截掉比如路径[1,1,2]会因为这个条件在第二层选第二个1时被误杀导致合法结果丢失。i start才是精确表达“当前层已经处理过相同值不需要再开一条重复分支”的正确写法。4. 复盘回溯题里最容易踩的五个坑4.1 忘了恢复现场输出一堆不应存在的路径这是新手翻车率最高的问题。路径数组path在递归进入时append返回时如果忘了pop上一层循环里的下一次迭代就会在一个“被加长”的基础上继续走。结果就是答案里出现大量长度超标、元素重复的路径。有个很有效的自查习惯在递归函数出口处path的长度应该和执行入口处一致。写递归时可以在心里默念“进函数时path多长出函数前path也得多长。”保持这个对称性现场恢复基本不会错。4.2 res.append(path)还是res.append(path[:])这个问题值得单独拿出来讲。Python里列表是引用类型直接appendpath等于往结果数组里塞入同一个对象的引用。而path在回溯过程中不断变化最终会被pop到只剩空数组那么所有“存进去的结果”最后看到的都是这个被反复修改的同一个对象。正确做法是res.append(path[:])把当前path的快照拷贝一份再存进去。类似的如果用其他语言也要注意是否需要深拷贝。我把这个坑列进“必踩”清单因为它不会立刻报错只会让输出结果变得匪夷所思。4.3 剪枝条件放在循环外还是循环内有些剪枝条件适合放在递归函数的最开头有些只能放在for循环内部。比如“当前累计和已经等于target”这种放在函数开头可以处理结束条件而“cur_sum candidates[i] target”这种依赖具体选项的只能在循环里逐项判断。如果错误地把依赖具体元素的剪枝条件放在递归入口处检查就会变成只有已经超出的节点被返回可具体是哪个选项导致超出的信息已经丢失想利用有序性提前break也就做不到了。正确逻辑是循环内发现当前元素会超出因为是排序数组直接break如果整个路径层都没希望那要靠递归入口处的结束条件兜底。4.4 递归深度过大与超时问题回溯的递归深度一般等于路径长度。数组长度几十个时递归深度不算大但组合类问题如果n到几百单纯回溯就可能超时甚至Python会报RecursionError。遇到这种情况先想两件事第一是不是剪枝力度不够很多无效分支还在硬搜第二题目是不是根本不适合用回溯而应该用动态规划或贪心。如果确认就是要用回溯可以临时调大递归深度限制import sys sys.setrecursionlimit(10000)这只适合偶尔的情况不要把它当成常规解法。真正稳的解法还是靠剪枝和合理设计状态维度。4.5 去重条件写成了i 0导致误伤前面组合总和II里强调过去重条件要写成i start不是i 0。这里再深挖一下为什么i 0会误伤因为i 0针对的是“数组全局下标”它不知道当前元素是不是本层第一次出现。如果数组里有两个相同的数字[1,1,2]路径[1,1,2]本身是合法结果但第二层选第二个1时i 0成立且candidates[i] candidates[i-1]成立于是这个合法分支被砍掉了。i start的含义是只有在同一层循环中已经处理过某个数字后面再遇到相同数字才跳过。不同层级之间的重复数字不受影响因为start会随递归深入而增大第二层的start1所以选第二个1时i1不满足i start可以正常进入。一个等号之差就是正确解和少解的差别。5. 回溯法、DFS和动态规划别混着用5.1 回溯和DFS一个侧重遍历一个侧重搜索与恢复DFS深度优先搜索是一种图遍历策略它强调沿着一条路径走到底再回头用于遍历整棵树或图。回溯则是在DFS的基础上增加了两个东西状态记录与恢复、剪枝判断。举个直观对比求一个矩阵里所有连通块这是DFS遍历过的格子标记为已访问即可不需要撤销标记因为连通块问题不关心路径的中间状态但如果是找一条从左上角到右下角且不经过障碍的路径这时路径本身是有顺序的走出死路后必须撤销刚才的标记让另一条分支还能经过这个格子——这就是回溯。换句话说DFS是“探索”的骨架回溯是“探索带记忆和反悔”的完整策略。很多回溯题的地基就是DFS但只有DFS而没有撤销操作解不出来。5.2 回溯和动态规划求“所有解”还是求“最优解”动态规划和回溯面对的都是决策过程但目标完全不同。动态规划关心的是“最优值是多少”或“方案总数是多少”它依赖重叠子问题和最优子结构用状态转移避免重复计算。回溯关心的则是“把所有解都列出来”它枚举整个解空间不依赖最优子结构。举例爬楼梯问题DP能快速算出一共有多少种爬法但如果要“打印出所有具体的爬楼梯步骤”DP就不够用得回溯来枚举具体方案。这里有一个选型判断题目问“有多少种”“最大值”“最小值”且状态重叠明显优先DP题目问“列出所有方案”“输出所有路径”用回溯。如果题目既要求所有方案又担心重复状态太多可以用记忆化优化回溯但这就是比较进阶的写法了。5.3 选型速查表题目特征优先使用的方案理由输出所有排列/组合/子集回溯解空间枚举是核心需求求方案数量且子问题重叠动态规划状态压缩避免重复计算找一条可行路径BFS或DFS更关注可达性而非枚举找最短路径BFS或Dijkstra层级扩展天然保证最短棋盘放置类最优化回溯剪枝候选选择多剪枝空间大求最优值且可分割贪心每一步局部最优即全局最优不要把回溯当成万能工具。它擅长解决的是“小规模枚举多重约束”的问题一旦状态空间太大还是要考虑更高效的数学模型。6. 从“初识”到“熟练”我的几个练习建议6.1 练习顺序先把“老三样”做扎实如果让我给一个练习路径我会把回溯题分成三组梯度。第一组是组合、排列、子集这三个基础题型。它们撑起了回溯的绝大多数套路用来练模板、练状态还原、练start和used的用法。第二组是棋盘类和搜索类比如N皇后、数独、单词搜索这些题更强调多维度约束判断练的是“剪枝条件怎么写才不重不漏”。第三组是字符串和构造类比如括号生成、分割回文串、复原IP地址它们需要你在构造过程中动态判断合法性对问题建模能力要求更高。按这个顺序刷每一次都建立在上一次的基础上不会一开始就被复杂的多人棋类题劝退。6.2 写代码前先把决策树画出来不管题目看起来多熟我都建议先在草稿纸上画三层决策树。画的时候要把“当前层可选什么”“选择后下一层可选范围怎么变化”“哪个条件能提前终止”写清楚。这个习惯对新手尤其有效。很多回溯代码写错不是语法问题而是对递归状态的流动没有概念。纸上画出树之后代码里每一步对应的就是树上的一次移动调试时也能更精准地定位问题。我通常还会顺手写出参数表递归函数需要哪些参数来刻画状态哪些参数跨层传递时要保持不变哪些参数进入递归时要增加把参数表列完再写代码基本一遍就能过。6.3 一个能让代码更稳的小习惯把回溯看成一进一出的对称操作最后分享一个改变我调试效率的小技巧。每次写回溯函数时我会刻意保持“进入分支时的状态”和“离开分支时的状态”完全一致。也就是说凡是进入递归前对数据结构做的修改返回后必须做对称的恢复。这件事听起来简单但实际上链条可能很长修改path、修改used、修改局部变量甚至修改某些全局计数。漏掉任何一步后续分支都会出问题。写完之后我会快速检查一遍所有在backtrack调用之前发生的修改是否都在调用之后被还原。这个习惯帮我省下大量debug时间。回溯法是我认为少数“代码看着不难但一调试就是半天”的算法因为你面对的不是语法错误而是状态机错误。认真对待每一步的进入和退出把分支去重逻辑想清楚这道坎很快就能迈过去。