后台收到不少同学私信说《代码随想录》刷到回溯篇就卡住了。说实话这个现象太正常了回溯算法在面试里是个分水岭会的人觉得它就是个“带撤销的递归模板”不会的人总觉得自己在瞎试、瞎碰。我当初第一次看Carl哥写的回溯基础时也是盯着那个for循环嵌套递归看了一下午才转过弯来。这篇博文我把回溯篇一的核心内容重新梳理一遍会讲清楚回溯到底在干什么、为什么模板要那样写、以及刷题时最容易翻车的几个细节。内容以Python为主但思路对所有语言通用C、Java的同学看模板也能直接迁移。适合刚刷完二叉树、准备进入回溯章节的读者也适合已经刷过几道回溯题但总感觉“代码能过、心里没底”的人。1. 回溯到底在解决什么问题1.1 回溯和递归是一体两面很多人把递归和回溯当成两个东西学其实回溯就是递归的一种应用形态。递归的特点是“函数调用自己”一层层向下钻回溯则是向下钻的过程中每层做了一次选择如果发现这条路走不通或者已经收集完一个结果就撤销这一步的选择回到上一层重新选。这个“撤销”动作在代码里就是递归调用之后那一行path.pop()。如果没有这一行path会越积越长永远回不到上一层状态。我刚开始写回溯时经常忘记pop结果输出的结果里path一直累积整个集合全乱套。后来我每次写递归调用后都习惯性地补一句“恢复现场”就像玩魔方拧错一步要拧回去一样这一步才是“回溯”这个名字的由来。1.2 回溯算法能覆盖哪几类经典问题从刷题角度看回溯算法几乎都围绕四类题型展开组合问题N个数里按规则选K个数比如LeetCode 77。排列问题N个数按不同顺序排列比如LeetCode 46。切割问题一个字符串按某种规则切割比如分割回文串。子集问题N个数的所有子集。以及一些棋盘类问题比如N皇后、解数独它们本质上也是回溯只不过搜索空间更复杂。无论是哪一类核心流程都一样画出递归树树的每一层对应一次选择树的每条分支对应一个具体选项回溯就是做选择、递归、撤销这三个动作的循环。1.3 《代码随想录》回溯篇的编排逻辑Carl把回溯篇的基础内容放在递归和二叉树之后我觉得这个顺序是有讲究的。因为回溯本身就是一种深度优先遍历理解了二叉树的递归遍历再看回溯就会顺很多。回溯篇一通常先讲理论基础然后接组合问题、组合总和、电话号码字母组合这几道题循序渐进地把模板立起来。所以这一篇的重点不是刷多少题而是真正吃透那个固定套路。套路一旦通了后面做排列、子集、分割无非是换换参数和剪枝条件。2. 回溯法的标准模板一句话记住三部曲2.1 回溯三部曲逐条拆解很多资料会把回溯总结成三部曲我刷完几十道题之后觉得这个总结非常精准递归函数的参数和返回值一般不需要返回值记作None/void参数里必须带上“当前搜索到哪一层”的信息比如startIndex或used数组。终止条件什么时候说明一条路径搜索完了该收集结果了。单层搜索逻辑for循环横向遍历当前层的所有候选循环体里做处理、递归、撤销三步。理解三部曲的关键是把递归树画出来。树的根节点是初始状态每往下一层走就是一次递归调用每个节点内部都在执行一个for循环。for循环里的“处理节点”就是我们做的一个选择“递归”表示带着这个选择继续往下走“撤销”表示这个选择尝试完了回到本层状态再试下一个候选。2.2 一个可以直接抄的模板框架我自己写回溯题时几乎都是这个框架先把它贴出来def backtrack(参数): # 终止条件 if 满足终止条件: 收集结果 return # 单层搜索逻辑 for 候选 in 当前层的可选集合: 处理候选加入路径/做选择 backtrack(更新后的参数) # 递归进入下一层 撤销处理从路径中移除/恢复现场这个模板看着简单但里面的参数设计是真正的难点。startIndex控制组合问题里的取数范围避免出现[1,2]和[2,1]这种重复used数组控制排列问题里同一路径不能重用同一个元素。这两个东西用反了代码怎么写都会出问题。2.3 为什么startIndex和used数组是灵魂有同学问我为什么组合问题不能像排列那样每次从0开始遍历因为组合不区分顺序如果你从0开始选了1之后再选2和选了2之后再选1两条路径会产生同一个组合结果里就全是重复项。startIndex的作用就是“我只能往后面选不能回头选”这保证了组合结果里的元素是递增取出的天然去重。而排列问题恰恰相反顺序是有效的[1,2]和[2,1]是两个不同的答案所以每层都要从头扫描所有元素。但为了避免同一个元素在一个排列里出现两次就得用used数组标记本轮路径已经用过哪些元素。这两者一个限制“取值方向”一个限制“同一路径内的元素复用”是回溯参数设计的核心。3. 实战第一题组合问题LeetCode 773.1 题目与暴力解法的天花板先看最经典的一道给定两个整数n和k返回[1, n]中所有可能的k个数的组合。比如n4, k2答案就是[1,2] [1,3] [1,4] [2,3] [2,4] [3,4]。如果不用回溯最暴力的思路是写k层for循环可问题在于k是动态的输入。你写3层循环容易k10的时候怎么办总不能在代码里写10层for嵌套吧。回溯解决的就是“不知道有多少层循环”的问题用递归代替固定层数的循环每一层递归就是一层for循环循环的层数由k决定。3.2 回溯代码逐行拆解class Solution: def combine(self, n: int, k: int) - List[List[int]]: res [] path [] def backtrack(start: int) - None: 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这代码看着简单但每一行都要弄明白。path里存的是当前已选的数字长度正好是k时说明组合已经完整这里一定要path[:]拷贝一份放进res直接append(path)的话后面执行path.pop()会把结果里的元素也改掉最后res全变成空列表。这个坑我踩过一次之后再也没忘。backtrack(i 1)是关键选了当前数字i之后下一层只能从i 1开始选这样[1,2]会出现而[2,1]永远不会出现。path.pop()把当前数字移除回到上一层状态让for循环继续尝试下一个数字。3.3 剪枝优化写出教科书级别的边界上面的写法能过但不是最优。假设n5, k4当你path里已经有2个数字时剩余需要2个数字。如果当前i已经到5哪怕还没到for循环末尾也凑不齐4个数字了后面的循环全是无效尝试。剪枝后的for循环范围可以写成for i in range(start, n - (k - len(path)) 2):这个边界值我第一次看也懵推导其实很简单。当前path长度为len(path)还需要k - len(path)个数字。从i开始到n至少要剩下这么多数字所以n - i 1 k - len(path)也就是i n - (k - len(path)) 1。而Python的range(start, stop)是左闭右开stop要取n - (k - len(path)) 2才能把i n - (k - len(path)) 1包含进来。这样剪枝之后分支数量大幅减少。我实测过n20, k10的场景剪枝版本比不剪枝版本快了很多而且这个剪枝思路后面做组合总和、子集的时候都能复用建议直接背下来。4. 组合总和与去重最容易卡住的40题4.1 组合总和LeetCode 39终止条件不只看长度组合问题升级版candidates给你一个无重复元素的数组你可以无限重复选取其中的数字目标是找到所有和为target的组合。比如candidates[2,3,6,7]target7答案是[7]和[2,2,3]。这题和77最大的区别是终止条件不再是“path长度等于k”而是路径和等于target。因为可以重复取同一个数字下一层递归传入的startIndex还是当前i而不是i1这样就能实现“同一个元素无限次使用”。这也是我第一次接触“递归参数决定搜索范围”的活例子看一遍代码就懂了class Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: candidates.sort() res [] path [] def backtrack(start: int, total: int) - None: if total target: res.append(path[:]) return if total target: return for i in range(start, len(candidates)): if total candidates[i] target: break path.append(candidates[i]) backtrack(i, total candidates[i]) path.pop() backtrack(0, 0) return res注意这里我先对candidates排序然后在for循环里判断如果total candidates[i] target由于数组已经升序后面的候选只会更大直接break结束这一层循环。这就是剪枝的价值不排序的话只能continue效率和代码可读性都差一截。4.2 组合总和IILeetCode 40树层去重的两种写法这题是回溯里最典型的去重题candidates里存在重复元素而且每个数字在每个组合中只能使用一次。给定[10,1,2,7,6,1,5]和target8如果用朴素思路搜会得到重复的[1,7]这个1是第一个1或第二个1和[2,6]答案全重了。解决办法是先排序再在同一层for循环里跳过重复元素。关键判断是i start而不是i 0class Solution: def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]: candidates.sort() res [] path [] def backtrack(start: int, total: int) - None: if total target: res.append(path[:]) return if total target: return for i in range(start, len(candidates)): if i start and candidates[i] candidates[i - 1]: continue if total candidates[i] target: break path.append(candidates[i]) backtrack(i 1, total candidates[i]) path.pop() backtrack(0, 0) return res为什么必须是i start因为start是本层递归的起始下标。candidates[i] candidates[i-1]表示当前候选和前一个候选值相同但只有在同一层里才需要跳过在不同层递归中出现相同数值是允许的比如[1,1,6]中两个1分别来自不同层这是合法答案。如果写成i 0会误杀这种跨层使用重复元素的合法组合。4.3 树层去重和树枝去重的本质区别Carl在讲这题时反复强调“树层去重”和“树枝去重”的概念。树层去重指的是在同一层for循环里跳过重复候选这对应上面的i start写法树枝去重指的是在同一条递归路径上避免重复使用同一位置的元素这对应used数组。两个概念搞混是回溯去重题最大的坑。可以这样记startIndex去重天然适合组合问题因为组合不在乎顺序同层重复选相同值只会产生重复组合而used数组去重适合排列问题和需要严格区分元素位置的场景。40题由于每个元素只能用一次、且candidates里有重复值既需要排除同层重复又需要在每层递归时向后的方向前进所以用i start的写法最简洁如果改用used数组也完全可以只是代码会多一点。5. 排列与映射回溯的另一面5.1 全排列LeetCode 46为什么不用startIndex组合题里[1,2]和[2,1]是同一个东西但全排列里它们分别是两个独立答案。这就是为什么全排列的递归不能加startIndex限制方向而要在每一层从头遍历所有元素。同时为了不让同一个元素在一组排列里出现两次需要引入used数组记录本轮路径的使用情况。class Solution: def permute(self, nums: List[int]) - List[List[int]]: res [] path [] used [False] * len(nums) def backtrack() - None: 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我刚开始学排列时有个疑问为什么这里不需要startIndex光靠used不会导致重复吗其实used保证的是“同一个排列里每个元素只用一次”而startIndex保证的是“后面的选择只能从当前位置之后取”。排列需要的是前者而不是后者因为每次递归都是重新从头扫描所以[1,2]和[2,1]都会被生成这正是排列的定义。5.2 电话号码的字母组合LeetCode 17跨集合回溯这题输入一个数字字符串比如23数字2对应abc数字3对应def输出所有可能的字母组合。它不是在一个集合里选元素的组合而是每组映射各自取一个字符本质上是多个不同集合之间的笛卡尔积。处理方式和前面的组合、排列都不一样不需要startIndex因为不同集合之间不存在重复选同一集合的问题也不需要使用used数组因为每个数字按顺序只处理一次。递归参数只需要一个idx表示当前处理到第几个数字横向遍历的是当前按键对应的字母串class Solution: def letterCombinations(self, digits: str) - List[str]: if not digits: return [] mapping { 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz } res [] path [] def backtrack(idx: int) - None: if idx len(digits): res.append(.join(path)) return letters mapping[digits[idx]] for ch in letters: path.append(ch) backtrack(idx 1) path.pop() backtrack(0) return res这题的代码是最标准的“模板原样”终止条件是idx len(digits)处理完最后一个数字就收集结果for循环的遍历范围是当前层的可选字母集合递归参数idx 1表示进入下一个数字键。5.3 排列组合子集怎么选参数一张表说清楚刷到这里我发现所有回溯题其实就是在三个要素里组合选择遍历方向、去重方式、终止条件。我把它们整理成表格做题时直接对照判断题目类型遍历方向去重方式终止条件组合77startIndex向后天然不重复path长度等于k组合总和39startIndex可原地天然不重复路径和等于target组合总和II40startIndex向后同层跳过重复值路径和等于target全排列46每层从0开始used数组path长度等于数组长度电话号码17按idx切换集合不需要idx等于数字串长度子集问题其实也遵循这个逻辑只是终止条件变成“每层都收集一次path”具体可以留到回溯篇二再细聊。这张表是我在刷题复盘时自己总结的拿它去套题大部分回溯题都能在三分钟内确定参数结构。6. 刷题排坑实录与个人心得6.1 最常见的四个翻车点先说res.append(path[:])和res.append(path)的区别。这是所有初见回溯的人都会踩的坑包括我。直接放path是把引用放进列表后面path.pop()一执行刚存放的“结果”就跟着变了。刷题平台里最后输出一堆空列表多半就是这个原因。解决方案永远是拷贝Python写path[:]或path.copy()Java写new ArrayList(path)C写push_back(path)其实没问题但如果你用的是引用类型的成员变量也要注意拷贝时机。第二个坑是把i start写成i 0。在40题这种去重场景里i 0会把不同层之间的合法重复元素也拦掉导致漏解。我建议每次写去重条件时在注释里标一句“同一层跳过”一旦写错排查思路立刻清晰。第三个坑是剪枝位置的顺序。先剪枝再去重还是先去重再剪枝看起来无所谓实际有影响。如果先写if total candidates[i] target: break再写去重判断在某些用例下会因为提前break把后面本可以跳过的重复元素一起跳过了但整体不影响正确性只是可读性差。我个人的习惯是先做去重判断再做剪枝判断顺序稳定不容易乱。第四个坑是递归函数忘了return。有时候终止条件里收集完结果没写return函数会继续往下走进入for循环产生一堆错误又多余的递归调用。我复盘过自己的提交记录不少超时都是这个原因造成的所以终止条件后一定要记得 return。6.2 我在实际刷题中的复习方法我刷回溯专题时用过一个笨但有效的方法每道题先自己画递归树再对着树写代码。比如77题画出n4、k2的树之后你会直观看到为什么startIndex控制的是“树枝走向”为什么终止条件是len(path) k为什么剪枝要改for循环上限。画三张树图之后回溯的递归结构就长在脑子里了后面遇到复杂题也不慌。还有一个复盘技巧把做过的题按“组合型、排列型、子集型、映射型”四个文件夹分类每类记录模板差异。比如组合和子集用的都是startIndex区别只在收集结果的时机排列用used数组映射用idx。分类整理之后新题到手第一反应不是“怎么写”而是“它属于哪一类、参数怎么定”刷题速度明显提升。6.3 回溯篇之后还可以怎么扩展回溯篇一把组合、组合总和、去重、排列、映射这几类基础题型覆盖完就已经拿到了解决回溯问题的主干思路。接下来可以做两件事一是把子集问题、分割回文串、复原IP地址这几类衍生题型刷完它们的模板完全一致只是终止条件和收集结果的时机有变化二是挑战N皇后和解数独这类问题本质上还是回溯只不过选择空间变成二维棋盘画递归树时需要把棋盘状态还原好。我个人刷完N皇后之后再回头做组合题会觉得所有回溯题都特别清爽因为它们共享同一套骨架做选择、递归、撤销。最后分享一个小习惯每次提交通过之后我会在代码注释里写一行“这题的终止条件是什么、剪枝条件是什么”。下次复习时一眼就能回忆起来不用重新读一遍完整代码。这个习惯帮我省了大量反复刷题的时间也让我真正从“看题解”过渡到了“写题解”的水平。