后台收到不少同学私信，说《代码随想录》刷到回溯篇就卡住了。说实话这个现象太正常了，回溯算法在面试里是个分水岭：会的人觉得它就是个“带撤销的递归模板”，不会的人总觉得自己在瞎试、瞎碰。我当初第一次看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 77）

3.1 题目与暴力解法的天花板

先看最经典的一道：给定两个整数n和k，返回[1, n]中所有可能的k个数的组合。比如n=4, k=2，答案就是[1,2] [1,3] [1,4] [2,3] [2,4] [3,4]。

如果不用回溯，最暴力的思路是写k层for循环，可问题在于k是动态的输入。你写3层循环容易，k=10的时候怎么办？总不能在代码里写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 剪枝优化：写出教科书级别的边界

上面的写法能过，但不是最优。假设n=5, k=4，当你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包含进来。

这样剪枝之后，分支数量大幅减少。我实测过n=20, k=10的场景，剪枝版本比不剪枝版本快了很多，而且这个剪枝思路后面做组合总和、子集的时候都能复用，建议直接背下来。

4. 组合总和与去重：最容易卡住的40题

4.1 组合总和（LeetCode 39）：终止条件不只看长度

组合问题升级版：candidates给你一个无重复元素的数组，你可以无限重复选取其中的数字，目标是找到所有和为target的组合。比如candidates=[2,3,6,7]，target=7，答案是[7]和[2,2,3]。

这题和77最大的区别是：终止条件不再是“path长度等于k”，而是路径和等于target。因为可以重复取同一个数字，下一层递归传入的startIndex还是当前i而不是i+1，这样就能实现“同一个元素无限次使用”。这也是我第一次接触“递归参数决定搜索范围”的活例子，看一遍代码就懂了：

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 组合总和II（LeetCode 40）：树层去重的两种写法

这题是回溯里最典型的去重题：candidates里存在重复元素，而且每个数字在每个组合中只能使用一次。给定[10,1,2,7,6,1,5]和target=8，如果用朴素思路搜，会得到重复的[1,7]（这个1是第一个1或第二个1）和[2,6]，答案全重了。

解决办法是先排序，再在同一层for循环里跳过重复元素。关键判断是i > start而不是i > 0：

class 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 排列组合子集怎么选参数：一张表说清楚

刷到这里我发现所有回溯题其实就是在三个要素里组合选择：遍历方向、去重方式、终止条件。我把它们整理成表格，做题时直接对照判断：

子集问题其实也遵循这个逻辑，只是终止条件变成“每层都收集一次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题，画出n=4、k=2的树之后，你会直观看到为什么startIndex控制的是“树枝走向”，为什么终止条件是len(path) == k，为什么剪枝要改for循环上限。画三张树图之后，回溯的递归结构就长在脑子里了，后面遇到复杂题也不慌。

还有一个复盘技巧：把做过的题按“组合型、排列型、子集型、映射型”四个文件夹分类，每类记录模板差异。比如组合和子集用的都是startIndex，区别只在收集结果的时机；排列用used数组，映射用idx。分类整理之后，新题到手第一反应不是“怎么写”，而是“它属于哪一类、参数怎么定”，刷题速度明显提升。

6.3 回溯篇之后还可以怎么扩展

回溯篇（一）把组合、组合总和、去重、排列、映射这几类基础题型覆盖完，就已经拿到了解决回溯问题的主干思路。接下来可以做两件事：一是把子集问题、分割回文串、复原IP地址这几类衍生题型刷完，它们的模板完全一致，只是终止条件和收集结果的时机有变化；二是挑战N皇后和解数独，这类问题本质上还是回溯，只不过选择空间变成二维棋盘，画递归树时需要把棋盘状态还原好。我个人刷完N皇后之后再回头做组合题，会觉得所有回溯题都特别清爽，因为它们共享同一套骨架：做选择、递归、撤销。

最后分享一个小习惯：每次提交通过之后，我会在代码注释里写一行“这题的终止条件是什么、剪枝条件是什么”。下次复习时一眼就能回忆起来，不用重新读一遍完整代码。这个习惯帮我省了大量反复刷题的时间，也让我真正从“看题解”过渡到了“写题解”的水平。