回溯算法这个系列我是打算认真写的。原因很简单回溯算法在面试、竞赛、日常开发里出现频率太高了但很多初学者看题解能看懂自己写就翻车。这个part01我先把它最核心的思想、模板、几道发家题串一遍把我自己踩过的坑一并说出来。不搞流水账看完你能跟着思路自己写出来才是目的。我带的很多人在学习回溯时最大的困惑是看了十篇题解做十道新题还是不会。根本原因是没有理解回溯到底在干什么只是记住了代码长什么样。这篇文章我会从为什么需要回溯回溯的执行过程长什么样开始再给出一套可以套用的模板然后用三道经典问题做完整拆解最后把常见的翻车场景列成速查表。适合刚接触回溯、或者刷过几道题但总觉得没串通的读者。1. 回溯算法的本质一个有后悔药的暴力枚举1.1 从暴力破解说起很多算法的本质其实都是遍历回溯也不例外。它解决的是一类最朴素的问题把所有可能性全部试一遍找到满足条件的答案。这和暴力破译密码的思路是一样的——从00000试到99999总能撞到对的。但差别在哪呢用纯暴力枚举要把所有组合全部生成出来哪怕中途已经发现这条路走不通也得等它走完才算完。回溯则是在枚举的过程中每走一步都问一句这条路还有希望吗如果发现当前的路径已经不可能通向正确答案它不会继续傻走而是直接放弃这个分支回到上一个岔路口换一条路继续试。这个回到上一个岔路口的动作在代码里就是状态回退。我特别喜欢用一个走迷宫的类比来解释这件事。你在迷宫里面发现前面是死胡同你的第一反应是退回到最近的一个岔路口而不是重新回到入口再走一遍。回溯就是把这个人类直觉变成了一套系统化的算法机制。1.2 决策树视角回溯就是深度优先遍历一棵树想真正理解回溯最好的方式是画出它的决策树。举个例子求三个元素 [1, 2, 3] 的所有全排列。第一个位置你可以放三个数选完第一个之后第二个位置只能从剩余两个数里选选完第二个之后第三个位置只有一个数可放。这样的选择过程展开就是一棵三层的树第一层有三个分支选1、选2、选3第二层每个分支下又分出两个分支挑剩下两个数中的一个第三层只剩一个选择也就是叶子节点这棵树的叶子节点一共有 3×2×1 6 个恰好对应6种排列。回溯的遍历方式就是深度优先沿着一个分支一路走到底走到叶子节点记录答案然后返回上一层换一个分支继续走。这就是回溯这个名字的由来——往回走一步换个选择再试。注意深度优先搜索DFS和回溯不是同一个概念。DFS是一种图的遍历方式回溯通常认为是DFS在决策树/状态空间树上的应用。日常讨论中可以混着说但心里要清楚边界回溯一定带有做选择-撤销选择这两个动作单纯的DFS不一定有。1.3 什么问题可以用回溯解不是所有问题都适合用回溯。我总结了一个简单的判断标准满足这几条基本就是回溯的菜问题可以被拆分成若干步骤每一步都需要做出一个选择选择之间存在约束条件比如全排列中已经被选过的数不能再选选择的组合构成一个完整解需要把满足条件的完整解找出来按照这个标准最典型的回溯问题可以归为四类问题类型典型代表特点排列类全排列、N皇后变体重视顺序需要used数组标记已选元素组合类组合总和、组合总和II不重视顺序用start参数控制起点防止重复子集类子集、幂集收集所有中间路径不仅收集叶子节点棋盘/图类N皇后、解数独解空间是棋盘或网格状态掌握判断方法比背题型更重要。我在实战中最常遇到的情况是拿到题先想这能不能用动态规划其实回溯才是更直接的方案。回溯不要求问题有最优子结构也不要求无后效性它就是一个纯粹的枚举器只是枚举得很聪明。2. 回溯的代码骨架模式是固定的别再裸写递归了2.1 模板结构逐个拆解回溯算法经过这么多年的沉淀代码结构已经高度模板化。下面这个模板是我自己在实际中使用频率最高的也是我带人刷题时最推荐的一套。def backtrack(路径, 选择列表): if 满足结束条件: 记录答案 return for 选择 in 选择列表: 做选择: # 更新路径和状态 backtrack(路径, 新的选择列表) 撤销选择: # 恢复路径和状态就这三行核心逻辑80%的回溯题都能往里面套。关键在于搞清楚每一部分具体怎么写结束条件通常是路径长度达到目标长度比如全排列要求每个元素都用一次也可能是剩余目标值刚好为零比如组合总和题目要求加和等于target。结束条件决定了什么时候把当前结果记录下来。选择列表情况比较多。有的问题是可重复选择的比如组合总和里的每个元素可以不限次数使用有的问题是不可重复的比如全排列有的问题选择空间在缩小比如N皇后每一层只有某几列可用。选择列表的维护方式直接决定了这道题的难度。做选择与撤销选择这两步必须成对出现。做选择时把元素加入路径、把状态标记为已使用撤销时把元素弹出、把状态恢复为未使用。我用一句话来强调撤销的重要性回溯的一切魔法都建立在能回到过去之上不能回退的分支探索那叫DFS不叫回溯。2.2 为什么撤销操作是灵魂很多初学者写回溯经常遇到一个诡异的现象最后收集到的结果全是一模一样的空列表或者同一个列表而且数量还不对。十有八九是撤销操作出了问题。这里有一个非常关键的技术细节在大多数编程语言里向结果列表添加路径时如果直接添加引用那么路径后面被修改时结果列表里的记录也会一起变。因为大家都在引用同一个列表对象。我举个简单例子# 错误示范 result.append(path) # path后续被pop和append后result里的记录也会变 # 正确示范 result.append(path[:]) # 拷贝一份当前路径切断引用关系这个path[:]代表复制一份新的列表后面你对path做任何操作都不会影响已经存进result里的答案。同样如果你的路径是用字符串拼接的方式也要注意是否需要深拷贝。撤销操作的核心逻辑就是做选择时的所有状态变更都要在撤销时导回去。这包括路径列表的增和减标记数组used的true和false累计值比如当前总和的加和减我见过最典型的翻车场景是标记数组在撤销时忘了改回false结果下一层递归看不到这个元素产生大量漏解。排查半天最后发现就是少了一行used[i] False。2.3 画出递归树再动手写代码我一直建议带的人先画递归树再写代码不然容易卡在选择列表的维护上。画递归树的步骤很简单从空路径开始写出当前层所有可做的选择对每个选择把状态更新后写出下一层的选择列表一直画到叶子节点也就是满足结束条件的位置把满足条件的节点标记为答案画完之后你会发现递归树其实就决定了代码里的for循环怎么写、参数怎么传。很多写着卡壳的地方画一遍树自己就通了。我在实际刷题时遇到没思路的题第一反应就是在白板上画三层递归树把选择列表的变化过程标出来再动手写代码。磨刀不误砍柴工。3. 实操全排列、组合总和与子集的完整解法3.1 全排列入门必刷的第一道回溯题全排列是回溯算法里最基础、最经典的问题没有之一。题目描述很简单给定一个不含重复数字的数组返回所有可能的全排列。我直接给一套参考实现然后逐步拆解def permute(nums): result [] n len(nums) used [False] * n def backtrack(path): # 结束条件路径长度等于数组长度 if len(path) n: result.append(path[:]) # 注意拷贝 return for i in range(n): if used[i]: continue # 做选择 used[i] True path.append(nums[i]) backtrack(path) # 撤销选择 path.pop() used[i] False backtrack([]) return result这套代码怎么理解我放慢节奏讲path是当前已经选好的排列前缀used数组标记nums里的元素有没有被选过保证排列里不会出现重复元素当len(path) n说明所有位置都填好了一个完整排列诞生for循环尝试在当前层把每个还没用过的元素放到下一个位置你可以想象这个过程第一层递归三个数都可以选选了1之后第二层递归里used[0]已经是True所以只能选2或3选了2之后最后一层只能选3得到排列[1, 2, 3]。然后撤销到第二层换选3得到[1, 3, 2]。这就是回溯的执行流程。时间复杂度是O(n!)全排列本身就有n!种这个复杂度是跑不掉的。空间复杂度主要是递归栈深度O(n)加上存储答案的空间。如果面试答这个时间复杂度建议顺带说一句因为排列总数就是n!这个复杂度是最优可能下的必然代价。3.2 组合总和剪枝比穷举更重要组合总和这道题是另一个经典它的完整描述是给定一个无重复元素的数组candidates和一个目标数target找出candidates中所有可以使数字和为target的组合。candidates中的数字可以无限制重复使用。这道题有一个非常关键的细节组合不要求顺序[2, 2, 3]和[3, 2, 2]是同一个解。如果用全排列的思路去做会产生大量重复结果。解决办法是靠一个start索引限制每一层的选择只能从当前位置往后挑这样就确保了组合内部是有序的同一个组合只会被搜索到一次。来看代码def combinationSum(candidates, target): result [] def backtrack(start, path, remaining): if remaining 0: result.append(path[:]) return if remaining 0: return for i in range(start, len(candidates)): # 做选择 path.append(candidates[i]) backtrack(i, path, remaining - candidates[i]) # 撤销选择 path.pop() backtrack(0, [], target) return result注意几个关键点第一backtrack(i, ...)传的是i而不是i1因为题目允许元素重复使用。当前选了下标i的元素下一层仍然可以从下标i开始选。如果题目是每个元素只能用一次就要传i1。第二这里用remaining 0来做剪枝。意思是当前组合的累加和已经超过target这条路没必要继续走下去了直接return掉。这个剪枝条件虽然简单但能把许多不可能的分支提前掐断。第三如果你想做得更极致可以先把candidates排序然后在for循环里提前判断candidates.sort() def backtrack(start, path, remaining): if remaining 0: result.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] remaining: break # 因为数组有序后面的元素更大直接终止循环 path.append(candidates[i]) backtrack(i, path, remaining - candidates[i]) path.pop()这个优化很有效。排序之后一旦发现当前元素已经大于剩余目标值后面的元素肯定也大于整层循环直接终止不再做无意义的递归。3.3 子集问题答案藏在所有中间路径里排列和组合之外子集问题是第三类常见题型。子集问题的特征是你的答案不只在叶子节点每一个路径节点都是一个合法子集。比如求数组[1, 2, 3]的全部子集。答案包括空集、[1]、[2]、[3]、[1,2]、[1,3]、[2,3]、[1,2,3]。解法也不难只需要对模板做一个小改动在递归的每一层把当前path记录下来而不只是退出时才记录。def subsets(nums): result [] def backtrack(start, path): result.append(path[:]) # 每个节点都是子集 for i in range(start, len(nums)): path.append(nums[i]) backtrack(i 1, path) path.pop() backtrack(0, []) return result子集问题的时间复杂度是O(2^n)因为子集总数是2^n。这个问题的变种很多比如子集去重先排序同一层跳过相同元素求排列的变种等等。弄懂上面这三道题你已经把回溯的核心用法掌握了至少一半。3.4 排列、组合、子集三类问题的差异对照我用一张表把这三类问题最核心的区别列出来方便对照记忆对比维度排列问题组合问题子集问题是否强调顺序强调[1,2]和[2,1]不同不强调[1,2]和[2,1]相同不强调选择列表维护每一层都是全体元素靠used去重只能从start往后选避免重复组合只能从start往后选答案收集位置到达终点叶子节点到达终点每一层节点都是答案典型结束条件path长度 nremaining 0不需要额外结束条件常用参数used数组start索引start索引这个对照表是我刷了上百道回溯题自己总结的。面对一道新回溯题第一步先判断它属于哪一类然后直接用对应的那套模板去套能省下大量试错时间。3.5 进阶场景组合总和II的去重逻辑组合总和还有一道升级版组合总和IIcandidates里可能有重复的数字每个数字只能用一次要求返回的组合不能重复。这道题把很多初学者卡死因为它需要在回溯过程中做同一层去重。我直接说解法核心先把candidates排序让相同的数字靠在一起在for循环里如果i start且candidates[i] candidates[i-1]直接跳过为什么排序之后就方便了因为排序后相同的元素在数组里是连续的。在同一层递归里如果当前元素和上一个元素相同说明在上一个元素的分支已经处理过这个值的所有可能性当前分支就是重复的直接continue掉。def combinationSum2(candidates, target): candidates.sort() result [] def backtrack(start, path, remaining): if remaining 0: result.append(path[:]) return for i in range(start, len(candidates)): if i start and candidates[i] candidates[i-1]: continue # 同一层去重 if candidates[i] remaining: break # 有序剪枝 path.append(candidates[i]) backtrack(i 1, path, remaining - candidates[i]) # 每个元素只能用一次 path.pop() backtrack(0, [], target) return result这里要特别注意去重条件里的i start。它表示只有同一层递归内才做去重如果是不同层即使元素值相同也允许选。比如[2, 2, 3]这个组合里两个2第一个2是第二层选的第二个2是第三层选的它们在不同层不会触发去重条件。这个细节一旦写错要么漏解要么去重失败。我当初就在这个i start上栽过一次排查了很久才发现是自己把条件写成了i 0导致不同层的重复选择也被拦掉了。4. 回溯算法的时间复杂度和优化空间4.1 复杂度分析怎么算回溯的开销回溯算法的复杂度分析比普通算法复杂一些因为它的实际开销和剪枝条件强相关。最稳妥的做法是分析解空间的大小再加上生成单个解的开销。以全排列为例解空间大小是n!每个解是长度n的列表记录答案需要O(n)时间所以总复杂度是O(n·n!)。组合总和这类问题最坏情况下的解空间大小呈指数级可以认为是O(2^n)级别的上界但实际因为剪枝往往远小于这个上界。我通常的建议是面试中被问复杂度先给出理论上界再说明剪枝对实际运行时间的影响。比如组合总和最坏情况是指数级但在排序剪枝之后实际搜索空间小很多很多分支在第一层循环就被截断了。这样回答显得你对算法有真正理解不是背答案。4.2 剪枝的核心逻辑提前结束注定失败的分支我把回溯优化的一句话心得放在这里能剪枝的地方一定要剪枝剪枝的时机优先级最高。判断是否终止一个分支可以在三个位置入口剪枝进入本层递归时判断状态是否已经不可能达到目标循环剪枝for循环内、做出选择之前判断当前选择是否合法、是否值得深入出口剪枝做出选择后、进入下一层之前直接判断还没递归就知道结果的路径以组合总和为例最有效的剪枝就是先把数组排序在循环内用candidates[i] remaining直接break。这属于第二类剪枝把一整层循环提前结束效果立竿见影。我在本地实测过排序剪枝对target较大的测试用例运行时间能减少一个数量级。还有一个很实用的技巧剪枝条件写在递归函数入口往往比写在循环内部更容易理解和维护。比如N皇后问题入口处检查当前放置是否合法不合法直接return代码结构非常清晰。5. 常见问题与排查技巧实录5.1 结果全是空列表或者全是同一个列表这个现象我在带人时遇到的频率排第一。原因我在前面讲过直接result.append(path)存储的是引用后续path变了结果也变了。解决办法就是拷贝一份Python用path[:]Java用new ArrayList(path)。如果你用Go也要注意切片是引用类型append(result, path)之后path再被修改result里的记录也会变。这一点在Go里特别容易踩因为Go的切片底层共享数组拷贝要手动append([]int{}, path...)。5.2 重复解怎么也去不掉产生重复解通常有两个来源第一同一层选了相同的元素。解决思路就是前面讲的排序跳过相邻相同元素。第二组合问题没用start索引导致顺序不同但组合相同的解被重复记录。解决思路是用start索引每次从当前位置往后选强制组合的顺序单调递增。排查的时候先把递归树画出来看重复解出现在哪一层。如果两个重复解是路径相同但顺序不同那就是start的问题如果同一层出现了值相同的分支那就是去重条件没有生效。5.3 怎么用打印来调试回溯过程回溯过程看不见摸不着光靠脑子想很难定位问题。我调试回溯题时经常写一个带深度的打印效果很好def backtrack(path, remaining, depth): print( * depth, f当前path{path}, remaining{remaining}) if remaining 0: result.append(path[:]) return for i in range(start, len(nums)): path.append(nums[i]) backtrack(i, path, remaining - nums[i], depth 1) path.pop()这样每次递归调用都会缩进一层输出看起来就像一棵树。一眼就能看出某个分支为什么没有继续下去、某个分支为什么走到了错误的结果。在刷题调试阶段这个手段比断点调试更直观。排除了直观问题之后再去看代码重点检查三件事撤销操作是否和做选择完全对称剪枝条件用的是还是差一个等号结果完全不同递归传参是i还是i1这决定了元素能否重复使用5.4 递归太深怎么优化回溯本身的递归深度一般不会太深N皇后到100层以上就很少见了。但如果递归深度真的很大有几种思路把递归改成显式栈的迭代写法避免函数调用栈溢出尝试用更有效的剪枝降低递归层数检查是否选择了错误的数据结构比如用全局变量维护状态能减少参数传递开销不过坦白说回溯面试题里深度爆炸的场景很罕见把精力花在剪枝和去重上更划算。递归栈溢出更多是竞赛题或者海量数据场景才会遇到。5.5 一条关于变量作用域的忠告Python里有一个很隐蔽的坑如果你在函数内部直接用result.append(...)没问题但如果你在嵌套函数里对result进行重新赋值比如result result [path]Python会认为你定义了一个新的局部变量result然后报UnboundLocalError。解决办法是在嵌套函数外用nonlocal声明或者干脆用result.append这种原地修改方式。这种问题看起来跟回溯算法无关但因为回溯本身重度依赖递归嵌套函数实际遇到频率不低。我建议统一写成原地修改避免在调试回溯逻辑时被语言特性干扰。6. 我的一点实操体会回溯算法入门的时候最容易犯的一个错误是看完题解觉得懂了合上书自己写就卡在选择列表怎么维护上。我想说的是这太正常了。回溯的抽象层次比普通递归高一层它同时要你管理状态、选择、撤销、剪枝四个维度大脑短期处理不了这么多信息唯一的办法就是纸上画递归树一遍不行画两遍。我自己从看题解到独立写出全排列花了差不多两天从会一道题到会一类题又花了大概一周。中间全靠把递归树画熟、把模板套熟这两个笨办法。我强烈建议你自己把全排列、组合总和这两道题不借助任何参考从头默写到通过。这个过程你可能会写三遍、五遍但每错一次你对撤销选择和选择列表这两个概念的理解都会加深一层。等你能闭着眼写出这两道题再看回溯的其他题型会发现只是换了个壳核心还是那几个动作。下一篇我会继续往深层走把回溯在棋盘类问题上的应用展开讲比如N皇后、数独这类需要二维状态维护的题目。能把排列、组合这两类吃透后面的路会顺畅很多。你先动手把代码跑起来有任何问题欢迎在评论区拿你的打印输出截图来讨论。