回溯算法这个东西真的是“不学觉得难学了觉得更绕”。前些天在刷第19天打卡任务正好做到回溯算法part01从组合问题开始入手。如果你也卡在这一部分觉得递归里塞循环、循环里再套递归边界条件一多就头晕那这篇我想把“part01应该建立起来的东西”一次讲透。先说清楚本篇目标不是把回溯的全部套路一股脑倒给你而是解决一个最核心的困惑——回溯到底是什么、它凭什么能用一套模板解一堆问题、模板每一步为什么非得写在那里。搞懂了这些后面写排列、子集、棋盘、切割各类题目你只是在往模板里填不同条件而已。1. 回溯算法在解哪一类问题——先别急着背模板1.1 暴力枚举办不到的事回溯为什么就能办到先说一个很朴素的问题组合的场景。比如从[1,2,3,4]里选2个数列出所有组合。你会写两层for循环。那如果选3个数呢三层for循环。选K个数呢你没法在代码里动态地写K层for循环。于是遇到这种“循环嵌套层数不确定”的问题普通暴力就卡住了。回溯的破局思路比较特别它不直接在代码里写死循环层数而是把“每一层循环”变成“递归的每一层”。循环要几层就让递归几次。这就是回溯能处理N选K这类问题的根本原因。从本质上说回溯就是一种系统化的暴力搜索。它把穷举的过程拆成一步步“做选择”然后走到底、没路就回头换一条路再走。所以它解决的是“在多个阶段分别面临多个选项时找出所有满足条件的组合方式”的问题。这类问题有一个共同特征解是一个序列或集合而每一步的选择都会影响后续的选择范围。1.2 经典题型家族part01先认个脸学习回溯最常见的几个题型家族你可以先记住组合类从N个元素中选K个不考虑顺序。代表题就是LeetCode 77。排列类N个元素的全排列顺序不同算不同结果。代表题是LeetCode 46。子集类把集合的所有子集枚举出来。代表题是LeetCode 78。切割/划分问题一个字符串能有哪些合法分割方式。代表题如分割回文串。棋盘/网格搜索类N皇后、数独、单词搜索一类需要逐个格子尝试。第一篇通常以组合问题切入因为它是最小的、结构最清晰的样本没有重复元素、没有顺序要求、选择范围固定。把组合问题的回溯跑通其他题型的差异点就变得容易定位了。1.3 解空间为什么画出来是一棵树回溯的全部奥妙都藏在一棵树上。以[1,2,3,4]选2个数为例第一层你可以选1、2、3、4选了1之后第二层只能从2、3、4里选选了2之后第二层只能从3、4里选……如果你把所有可能的尝试路径画出来会发现它是一个向右侧倾斜的树状结构第一层1 → 2 → 3 → 4每个节点下面再接上“它之后的所有元素”树的每个分支代表一种“选择路径”树的每条从根到叶子节点的路径就是一个组合结果。为什么用树来理解很重要因为递归其实就是“沿着一条路径走到叶子然后返回上一个分岔口换另一条路”。这不就是树的深度优先遍历吗所以回溯 DFS 状态恢复这句话不是修辞而是字面上的工作机制。2. 回溯的底层运转机制——状态、选择列表、撤销2.1 把“走迷宫”翻译成代码逻辑想象你在走一个迷宫手里拿着一个本子记录走过的路。每一步到你面前都有好几条岔路你会做三件事选一条路在本子上记下你选了这条。沿着这条路走到下一个岔路口重复上面的过程。此路不通或已经走完所有可能顺着原路退回来在本子上擦掉刚才记下的路换一条岔路再试。“本子上记路”就是路径path当前可以走的岔路就是选择列表choices退回来擦掉记录就是撤销选择undo。对应到代码里本子就是数组或字符串。每递归进入下一层就往path里加入当前选择递归返回后再从path里把最后一个元素弹出。这个“加入—递归—弹出”的节奏就是回溯的全部代码骨架。2.2 递归怎么帮你自动完成“回头”很多人第一次接触回溯会疑惑为什么递归返回后程序会到“上一层”继续执行因为递归函数调用是有栈结构的。每调用一次函数系统会为这次调用保存现场——包括当前函数的局部变量、执行到哪一行。当内层递归执行完返回时系统自动恢复外层的现场代码继续从调用点往下执行。所以“回溯”过程中的“返回上一层”不是你自己手动写逻辑跳转的而是函数调用栈天然具备的能力。你只需要负责两件事递归之前做选择递归之后撤销选择。系统会自动带你回到决策点。这个机制想通了你就明白为什么回溯代码看起来总是一段“对称”的结构了选择 递归 撤销选择三者缺一不可。2.3 撤销选择不是洁癖而是生存必需很多人写递归时想偷懒既然path每次都在增加那我不删掉最后一个是会怎样会出大问题。假设path是一个全局列表第一层选了1递归返回后如果不删1第二层选2时path里就会残留[1,2]结果变成了[1,2,2]甚至更乱。更深入的例子path如果作为参数传递在Python里传的是引用在Java里如果传的是ArrayList那也是同一份对象的引用。不显式撤销所有分支共享同一个列表最终收集结果全是同一个列表的最终状态。我在初学阶段就踩过这个坑。当时用Java写结果List里存了5个一模一样的数组查了半天才发现是引用共享。后来我总结出一个习惯所有作为“路径”的容器在存储最终结果的时候必须新建一份拷贝在递归回溯过程中该删就删绝不手软。3. 回溯框架模板的推演——以组合问题为例子3.1 题目与场景LeetCode 77 组合给定两个整数n和k返回[1, n]中所有可能的K个数的组合。这个题目是回溯part01的标准入门题。n和k都不大但足以演示回溯的一切核心要素。输入n4, k2输出应该是[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]注意这里[1,2]和[2,1]是同一个组合题目要求组合不考虑顺序。3.2 基础代码逐行拆解先给出一个最朴素的版本后续再优化剪枝def combine(n: int, k: int) - list[list[int]]: result [] path [] def backtrack(start: int) - None: # 基线条件path长度达到k收集结果 if len(path) k: result.append(path[:]) # 必须拷贝 return # 当前层可选的数字范围 for i in range(start, n 1): path.append(i) # 做选择 backtrack(i 1) # 递归进入下一层下一个数必须从i1开始 path.pop() # 撤销选择 backtrack(1) return result这段代码看起来简单每一行背后的意图都值得深挖。3.3 start参数为什么它是组合问题的灵魂上面的代码最容易被忽略的一个参数就是start。选完一个数之后下一层递归的搜索起点必须变成start i 1不能从1重新开始。原因很简单组合问题不关注顺序。你选了1之后再选2和选了2之后再选1是同一个结果。如果第二层还从1开始搜就会产生[1,1]重复选自己和[2,1]和[1,2]重复这类多余分支。所以start的存在本质上是为了避免重复组合。它把解空间从完整的N叉树砍成了一个“只向后看、不回头”的搜索树这样一来枚举的顺序被强制定为从小到大每个组合只会出现一次。排列问题为什么没有start因为排列是[1,2]和[2,1]都算不同结果当然要从头搜还得加个used数组来防止重复使用同一个元素。这是part01之后的话题现在先不展开。3.4 用“树形图调试法”代替瞎打日志我学回溯时养成的调试习惯是在代码里加一个depth参数打印缩进像画树一样查看每一层的选择与回溯。def backtrack(start: int, depth: int) - None: print( * depth f进入: start{start}, path{path}) if len(path) k: result.append(path[:]) print( * depth f收集结果: {path}) return for i in range(start, n 1): path.append(i) print( * depth f选择 {i} - {path}) backtrack(i 1, depth 1) path.pop() print( * depth f撤销 {i} - {path})运行后的输出长这样节选进入: start1, path[] 选择 1 - [1] 进入: start2, path[1] 选择 2 - [1, 2] 进入: start3, path[1, 2] 收集结果: [1, 2] 撤销 2 - [1] 选择 3 - [1, 3] ... 撤销 1 - [] 选择 2 - [2] ...当你把递归的进入、选择、撤销都打印出来整棵搜索树就浮出水面了。哪个分支多搜了、哪里没有回溯一目了然。这个调试方法我一直沿用到现在不止回溯写树的DFS、图搜索都用得上。提示遇到回溯题目卡壳不要光靠眼睛看代码把树打印出来是最快的定位方式。4. 剪枝优化——怎么砍掉必然无解的分支4.1 剪枝的本质提前判断终止递归回溯是暴力搜索但它不等于傻搜。很多时候根据当前信息就能判断“这条路就算走到底也凑不出结果”这时直接停止递归跳过这个分支。这个动作就是剪枝。剪枝的位置通常在选择循环里判断方式就是“当前已有元素 剩余可选元素 目标数量”。如果不够后面的所有递归都是无意义的直接break或continue。4.2 组合问题的经典剪枝剩余元素不够选延续上面的n4, k2例子。假设当前在for循环里start3path已经有个[2]目标长度是2。你还能选吗可以3和4都至少能凑成一组。但当start4时path为[3]循环到i4选了4之后刚好凑齐。可如果你在某个状态path为空start4那你还能选吗显然不能了——后面只剩下4一个数凑不出2个。所以剪枝条件可以写成for i in range(start, n 1): # 如果剩余元素数量不足以填满path直接跳过 if n - i 1 k - len(path): break path.append(i) backtrack(i 1) path.pop()这里解释一下公式n - i 1从i到n一共有多少个数。k - len(path)path还差多少个数才能满员。如果“剩下的全部数都加上”都填不满目标那以i为起点的所有分支必然无解没必要递归进去了。放到上面的例子n4, k2当start4时path为空循环到i44-411而2 - 0 21 2直接break。等于把原先对4做第一层选择的整棵子树都砍掉了——很划算。4.3 剪错了会怎样一个反例告诉你为什么条件必须严格剪枝最怕的不是不剪而是剪错了把还能出结果的分支给砍了。比如有人会把条件写成if len(path) 1 k: continue这个意思是“当前位置只剩一个数可选就不够”但这不是题目要求的。数量判断必须用“剩余可选元素总数”而不是“当前层可选的一个元素”。如果条件过严可能漏掉正确组合如果条件过松剪枝没效果。我见过不少人一开始把剪枝条件写成了if n - i k - len(path)把n - i 1错写成n - i导致边界情况少算了一个元素——当i n时n - n 0永远触发剪枝最后一个组合比如[4, ...]相关分支就没搜到。这种错很难查因为大多数测试用例不会只查最后一个组合。所以我的建议是第一次写先不要把剪枝写进去先把无剪枝版本跑通再用小规模输入验证剪枝后的结果完全一致然后才放心合入。4.4 剪枝的收益真实对比一下拿n4, k2来说不剪枝递归节点总数是第一层尝试4个数。第二层分别尝试3、2、1、0个数。总递归次数4 3 2 1 10次。剪枝之后start4的第一层被剪掉少递归1次变成9次。差距还小。但当n20, k5时剪枝的收益就大了。不剪枝的搜索空间接近 C(20,5) 的几倍甚至几十倍剪枝能减少大量无效递归。回溯题目的剪枝非常依赖问题特征。组合问题是“数量不够”剪枝排列问题可能用“元素是否已使用”剪枝棋盘类问题用“当前位置能否放置”剪枝。核心一致在进入递归之前判断这条路是否可能产生解不可能就跳过。5. 回溯的去重问题——part01最容易忽略的深水区5.1 同一层去重 vs 同一分支去重part01写过的题目一般是“无重复元素”的组合但这不代表去重可以等以后再学。因为回溯题目里去重是出错率最高的部分而且它的坑从第一天就会遇到。先明确两个概念同一分支去重沿着一条路径往下走同一个元素只允许被使用一次。比如[1,1,2]里同一个位置上的1不能同时选两次。同一层去重在for循环里如果这一层已经尝试过某个值而下一个迭代的值和它相同那就可以跳过因为这个分支会生成完全重复的结果。part01的组合问题通常没有重复元素同一层去重不常用。但如果你刷题进度稍快马上会碰到“组合总和II”这种带重复元素的题目。到时候你会发现光靠start不够了必须同时处理横向重复。5.2 为什么“排序 跳过”是通用做法处理同一层去重最常用的套路是先把候选数组排序。在for循环里如果i start且candidates[i] candidates[i-1]直接跳过。这里的candidates[i] candidates[i-1]判断的是“当前值和本层上一个已经尝试过的值相同”。因为已经排序过相同元素必然相邻一次判断就能拦下所有重复。为什么不看used数组也能去重因为排序后如果前一个相同元素还在可用的位置但本层已经选过它那么这个分支和“选后一个相同元素”生成的结果是一模一样的。既然要求组合不重复后者就可以被放弃。注意排序跳过的去重逻辑必须在每一层开始时都生效而不是只在第一层判断。如果你只在根节点判断内层还是会产生大量重复组合。5.3 used数组到底什么时候用还有一种更通用但稍微繁琐的做法维护一个used布尔数组。它主要用于排列问题因为排列要考虑顺序[1,1,2]和[1,2,1]是不同排列不能简单按值跳过而需要精确标记“这个位置的元素是否已经在当前路径上被用过”。used数组去重的判断条件是if used[i]: continue if i 0 and nums[i] nums[i-1] and not used[i-1]: continue第二个条件理解起来有点绕如果当前元素和前一个元素相同且前一个元素在同一层搜索时没有被使用过说明前面已经有一个相同值被优先尝试过了当前这个就跳过。这条规则初看很反直觉但它保证了“相同值的元素在同一层只会被用一次”同时允许“相同值出现在不同层”例如排列里的[1a, 1b]和[1b, 1a]这种不同顺序。part01阶段你可以先记住结论等到part02做排列题时再回来对照验证。现在只要知道组合去重靠排序跳过排列去重靠排序used数组这就行了。6. part01阶段最容易踩的三个坑——从个人信息泄露级别的教训说起6.1 收集结果时写了浅拷贝全result都是最终path的镜像这个问题我在前面提过一句但它值得单独拿出来说因为它真的是所有回溯初学者第一个碰到的“鬼打墙”。错误示范result.append(path) # 不是path[:]直接塞引用跑完之后你会发现result里全是最后一个path的状态比如[[3,4],[3,4],[3,4],[3,4],[3,4],[3,4]]。原因就是所有path都指向同一个列表对象后续回溯操作把这个对象改得面目全非之前“收集”的结果也跟着变了。正确写法是result.append(path[:])或result.append(list(path))本质是把当前快照复制一份。如果你想加深记忆我建议你故意写一次错的打印result看它怎么一点点被改掉。这种亲眼看状态污染的过程比看十遍文档都有用。6.2 在for循环里修改path没有用局部变量有些同学的代码习惯是把path做函数参数传递但使用的是修改式操作def backtrack(start, path): ... path path [i] # 这是新列表不污染原path backtrack(i 1, path)这种写法没用path.pop()但递归函数里的path已经变了并不会自动回到原状态因为外层path没变、内层拿到的是新列表所以“撤销”实际上没有发生。最终结果可能是对的因为新列表不共享但多了一大堆无用对象而且递归的path分支越来越少纯属无效搜索。回到最开始那个共识回溯要基于同一个path对象做“增删”操作而不是赋值新列表。赋值你是能算对部分结果但复杂状态一多就会炸。6.3 基线条件放的位置不对提前return导致漏解基准条件当path长度等于k时收集结果并return必须写在“进入for循环之前”而不是写在循环里面。有同学会把收集操作放在循环内部某个分支里比如for i in range(start, n1): path.append(i) if len(path) k: result.append(path[:]) backtrack(i1) path.pop()这样当path凑满时它还会继续进入下一层递归而下一层发现len(path)k不满足收集条件直接返回。结果也许没错但平白多了一次无用的递归更重要的是代码逻辑变得很不清晰后续一旦想加剪枝或去重这种混乱结构会非常难改。回溯的代码有一个不成文的好习惯开头先判断是否满足收集条件满足就收集并结束当前递归然后才进入for循环做选择。把这两件事分开边界就会非常干净。6.4 复杂度估算——别等超时才想起来回溯的复杂度往往是指数级part01题目规模小经常感觉不到。但心里一定要有个数。以组合问题为例无剪枝情况下递归次数的上界是C(n,k)乘以每层的一些系数整体复杂度接近O(C(n,k) * k)。也就是说一旦n到30、k到15计算结果瞬间爆炸。这也是为什么回溯题目的数据范围一般都很小n通常不超过20或30——范围一大回溯就无解了必须转动态规划或贪心。所以part01阶段做题不用太纠结超时更重要的是判断“这道题是不是回溯的菜”。怎么判断看题意是不是要求“枚举所有组合/排列/路径”且数据范围不超过几十。如果是回溯模板放心上如果n到几百那大概率不是用回溯解的别硬套。7. 这个模板怎么往“变形题”上面迁移——part01的延展思考7.1 组合总和不用固定长度的变体做过77题以后接下来最常见的变形是“组合总和”给定一个数组和target找出所有和等于target的组合。这里k变成了动态的“和等于target”而不是固定长度。模板变化很小基线条件从len(path) k变成当前sum target或sum target。递归时的参数多一个current_sum每次选择后累加。但是这里有个新课题数字能否重复使用如果可以重复下一层start就仍然是i而不是i1。这个变化是part01向part02过渡的导火索它提醒你选择列表的范围是由“能否重复使用”决定的而不是一成不变的。7.2 路径类问题坐标系里找所有路径回溯也常用于网格路径。从左上角走到右下角每次只能向右或向下要输出所有路径。此时path里的每个元素是坐标选择列表变成了“向右/向下”。如果你的递归函数定义成backtrack(row, col)那么每个状态的可选项就是固定的两个方向而不像组合问题那样是一个数组里的众多元素。路径类问题虽然脑子里想的是“图”但代码结构依然是回溯模板走到终点收集结果、探索所有方向、回退当前步。part02以后大概率会遇到这种题到时候你会发现模板没变变的是“选择列表怎么生成”。7.3 什么时候该用回溯什么时候该用动态规划这是一个必须尽早建立的判断力。回溯解决的是“找出所有解”动态规划解决的是“求最优解/解的数量”。比如“到达终点的所有不同路径数”是DP的菜因为只要数量但“列出所有具体路径”就必须回溯因为你得真的枚举每一条。这个判断看似简单实际做题时经常搞混。我的经验是如果题目问“多少种”“最大值”“最小值”“是否存在”先想DP和贪心如果问“具体是哪几条”“列出所有”“返回所有组合”回溯才是主角。8. 写在最后part01我最想让你带走的一件事回溯算法的第一部分关键不在代码量有多大而在于三个意识的建立。第一是树形意识。每当你在回溯题里迷路就在纸上把解空间树画出来。搜索树的每个节点是一个状态每条边是一次选择。递归是DFS回溯是DFS返回时的状态恢复。脑子里有这个画面代码再长也不会乱。第二是框架意识。回溯的模板是“路径、选择列表、结束条件”三件套。任何回溯题都逃不开这三样东西。做题前先问自己path存什么、每层的选择范围是什么、递归什么时候返回。第三是撤销意识。改动了共享状态就必须恢复这是回溯区别于普通递归的分水岭。宁可多写一行path.pop()也不要省这一行导致整个结果集崩溃。我个人在写回溯代码时有个习惯先把最朴素的版本写出来跑通再剪枝。因为剪枝、去重这些优化很容易掩盖逻辑错误。回溯这种“暴露问题于无形”的算法简洁是第一原则。如果你现在正在做day19这个节点不要急。part01能独立写出77题、并能完整解释出start和path.pop()的作用就已经很扎实了。后面排列、子集、棋盘、分割都是在这个框架上加条件而已。慢慢来树的画面一旦建立起来回溯的题感会在一周内突飞猛进。