回溯算法我愿称之为“暴力美学的极致”。很多人一听到“回溯”两个字就觉得头疼，觉得它又抽象又难写，什么递归、状态重置、剪枝，一堆概念叠在一起。但如果你真正把它拆开看，就会发现它本质上就是一个“有策略地穷举”的思维过程，你不需要一下子想出什么精妙的数学公式，你只需要学会如何把一个大问题拆成一模一样的小问题，再学会如何“反悔”。今天这篇day24笔记，我就把回溯算法从头到尾、从原理到模板、从经典题到剪枝优化，一次说透。
很多人分不清回溯和递归的关系，其实回溯是基于递归来实现的，递归是它的“壳”，而回溯是它的“魂”。我们日常写的DFS深度优先搜索，本质上就是回溯的一种体现。所以如果你国庆力扣刷题刷到“全排列”“组合总和”“子集”这类问题时感觉卡壳，不用怀疑自己的智商，绝大多数人都是卡在“为什么撤销这一步”这个坎上。
这篇我会先带你搭出回溯的通用模板，然后拆解组合、排列、子集、切割、棋盘这几大类高频题型的解法，后面再讲剪枝和去重这两个真正决定你能不能AC的关键。全程用大白话，配上代码和踩坑记录，保证你学完能直接上手写题。
1. 回溯算法的本质：把“反悔”变成一种搜索策略
1.1 从一次“走迷宫”说起
想象你在走一个迷宫，走到岔路口时你随便选了一条路走，结果走到死胡同了。这时候你怎么办？是不是退回到上一个岔路口，换一条路继续尝试？这个“退回去换条路走”的动作，就是回溯。
计算机里的回溯算法干的就是这件事，只不过它不是人肉走迷宫，而是通过递归这个机制，把每一步的选择和撤退都交给函数调用栈来管理。我们用代码去描述“我选了某个元素”这个状态，然后递归去探索后续所有的可能性，等这一条路探索完了，再把状态改回选之前的样子，继续尝试下一种可能性。
这个“改回选之前的样子”的操作，就是很多人常说的状态重置（backtrack）。它是回溯的灵魂所在，也是最容易被忽略、最容易写错的地方。一旦忘记重置，你会惊讶地发现，你的结果里出现了各种莫名其妙的重复组合，或者路径越攒越长。
1.2 回溯算法能解决哪四类问题
从刷题的角度来看，回溯算法的应用场景非常固定，LeetCode上的回溯题几乎逃不出这四类：
- 组合问题：从N个数中按一定规则选出K个数，比如“组合总和”。
- 切割问题：一个字符串按一定规则切割成若干子串，比如“分割回文串”。
- 子集问题：求一个集合的所有子集，比如“子集II”。
- 排列问题：N个数按一定顺序全排列，比如“全排列”。
另外还有一类棋盘类问题，比如N皇后、解数独，本质上也是回溯，只是每一层的选择变成了“在棋盘的某个位置放什么棋子”。你可以把棋盘问题理解为“组合/排列问题的空间升级版”。
1.3 为什么回溯不是简单的暴力枚举
暴力枚举和回溯算法的区别在于，暴力枚举会无差别地尝试所有可能，哪怕是已经可以判定走不通的情况，它也照样递归下去。而回溯算法往往带一个剪枝操作，在递归之前判断一下，发现这条路已经不可能产生合法结果，就直接放弃，不再往这个分支投递任何计算。
举个例子，你要在1到10这10个数里选3个数组成组合，并且要求组合的和不能超过5。如果你用纯暴力枚举，你会先选出(1,2,3)，发现和是6，超了，然后继续选(1,2,4)，又超了……所有组合都要算一遍。但如果用回溯加剪枝，一旦发现当前路径的和加上剩下最小的那个数都已经超过5，就直接return，后面的计算全部省掉。数据量小的题目也许看不出差异，数据量一旦上来，剪枝与否可能就是超时和秒过的区别。
2. 回溯算法的通用模板与核心框架
2.1 七行核心框架先背熟
我做深度优先搜索类题目做了几百道之后，总结出一个现象：所有的回溯题，代码骨架几乎是一模一样的。把这个模板背熟，往里面填逻辑就行。
用伪代码写的框架长这样：
def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择展开成Python代码，核心逻辑就是三步：
result = [] def backtrack(path, choices): if 终止条件: result.append(path[:]) # 注意是拷贝，不是直接append(path) return for i in range(len(choices)): # 剪枝条件，可以放在这里 路径做选择 backtrack(path, 新的choices) 撤销选择 backtrack([], 初始choices)这个模板里最关键的是两个动作：“做选择”和“撤销选择”。做选择时，我们要把当前元素加入path；撤销选择时，要把之前加入的元素弹出来。很多刚入门的朋友都会写出类似这样的错误：
result.append(path) # 错误写法这样写的结果是，最后result里面所有元素变成了同一个列表的引用，而由于回溯时path会被修改，你会发现最终结果是一堆重复的空列表或重复的排列。这里需要特别记住的是要append(path[:])，拷贝一份快照。
2.2 参数设计：哪些东西要在递归函数里传递
设计递归函数参数是个技术活。参数太多了，代码看起来很笨重；参数太少了，状态又传不完整。根据我的经验，回溯递归函数至少需要这几样东西：
- 当前位置或当前层数：用来判断递归何时终止。
- 当前路径path：记录了到目前为止做了哪些选择。
- 剩余可选项（或者可选范围）：告诉下一层递归，还有哪些选择可以做。通常用startIndex或者一个used数组来表示。
- 全局结果集合result：用来收集所有满足条件的路径。
我强烈建议把result定义为类属性或者全局变量，而不是在递归参数里传来传去。因为Python的函数参数传递机制里，列表是可变的，你传进递归的是引用，所以不在参数里传它完全没问题，反而能让代码更清爽。
2.3 递归终止条件怎么判断
终止条件一般分两种。
第一种是路径长度达到目标，比如组合问题要求选够K个数，排列问题要求排列长度等于数组长度，这种直接判断len(path)是否等于K即可。
第二种是遍历完了所有可选择的位置，比如子集问题，startIndex已经越界到了数组末尾以后。
还有一种稍微特殊的情况，是求和类问题（比如组合总和），当当前路径的和已经大于目标值时，即使路径长度还没达到K，也可以终止。这一条通常会和剪枝混在一起，但它本质上也是终止条件的一种表现形式。
3. 经典题型拆解：组合、子集、排列的三角关系
3.1 组合问题：startIndex控制的是“不回头”
组合问题是回溯里最基础、最核心的题型。它的特点是：顺序不重要，也就是(1,2)和(2,1)算同一种结果。所以我们需要用一个startIndex来确保递归下一层时，只能从当前位置的后面的元素开始选，这样就不会产生逆序组合。
看一道非常标准的题目：LeetCode 77 组合。给定n和k，返回1到n中所有可能的k个数的组合。
def combine(self, n: int, k: int) -> List[List[int]]: result = [] path = [] def backtrack(start): if len(path) == k: result.append(path[:]) return for i in range(start, n + 1): path.append(i) backtrack(i + 1) path.pop() backtrack(1) return result这段代码里只有一个精妙之处：backtrack(i + 1)。它保证了下一层递归的起始位置在i的后面，这样就天然避免了重复组合。如果你写成了backtrack(start + 1)，那(1,3)和(3,1)就会被算作两种不同的组合，结果必然出错。
3.2 子集问题：每次递归前都要记录当前状态
子集和组合非常相似，区别只在于：组合的终止条件是长度达到K，而子集则是每进入一层递归，就要把当前路径加入结果集。因为空集是子集，长度为1的集合也是子集，长度为2的也是子集，所有中间状态都是最终结果的一部分。
看看LeetCode 78 子集的写法：
def subsets(self, nums: List[int]) -> List[List[int]]: result = [] path = [] def backtrack(start): result.append(path[:]) # 每一层的path都是一个子集 for i in range(start, len(nums)): path.append(nums[i]) backtrack(i + 1) path.pop() backtrack(0) return result注意我把result.append(path[:])放在了for循环外面，这样保证进入某个节点时就先收集当前路径，然后再去遍历下一层的所有分支。如果你把它放在for循环里面，就会漏掉空集和每一层的前缀子集。
有个时候我看到有人把子集问题写成先按子集长度分组，每次调用一个不同长度的组合解法，也不是不行，但效率上完全没有必要。一次回溯就能把从0到N长度的子集全部收集齐，何苦写N遍循环呢？
3.3 排列问题：used数组而不是startIndex
排列问题和组合问题最大的区别在于：排列里(1,2)和(2,1)是两个不同的答案。所以startIndex这套“不能回头”的策略就行不通了，你得允许每一层递归都能从头开始选。
但这样又会出现新的问题，比如选了1之后，下一层还是可以选1，这就产生了重复排列。所以排列问题的核心是维护一个used数组，用来标记哪些元素已经被用过。每一层的for循环遍历的是整个数组，但是只跳过那些已经被用过的元素。
LeetCode 46 全排列的标准解法：
def permute(self, nums: List[int]) -> List[List[int]]: result = [] path = [] used = [False] * len(nums) def backtrack(): if len(path) == len(nums): result.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 result这段代码是我觉得全排列里最经典的写法。used数组在进入递归前标记为True，递归结束后恢复为False，这个True和False的反复横跳，就是“状态重置”最直观的体现。全排列题目看着花样多，实际上只要把used的标记和撤销写对了，剩下的都是体力活。
3.4 组合总和与剪枝的第一次相遇
到组合总和这道题，回溯开始展现出真正的威力。LeetCode 39 组合总和，给一个无重复元素的数组candidates和一个目标数target，找出所有可以使数字和为目标数的组合。candidates中的数字可以被无限重复选取。
这里和之前组合问题的区别是：同一元素可以重复使用。所以我们的递归下一层不能再从i+1开始，而要从i开始。但为了不产生(2,3)和(3,2)这种重复组合，还是要保留startIndex来控制方向。
标准的写法是这样：
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: result = [] path = [] def backtrack(start, current_sum): if current_sum > target: return if current_sum == target: result.append(path[:]) return for i in range(start, len(candidates)): path.append(candidates[i]) backtrack(i, current_sum + candidates[i]) path.pop() candidates.sort() backtrack(0, 0) return result这里有一个非常实用的剪枝点：先把candidates排序。排序之后，当for循环里某个元素加上当前和已经超过target，那后面的所有元素也一定会超过target，直接break。这样比递归进去再判断快很多。
有的资料会把剪枝条件写进递归函数开头，就是current_sum > target就return。这个逻辑没错，但效率不如在for循环里提前判断。我实测在数据量大的情况下，提前剪枝至少省掉一半的无效递归调用。
4. 去重实践：为什么你已经回溯却还是一堆重复答案
4.1 用排序加相邻元素比较实现横向去重
如果要给回溯算法找一个最容易出错的考点，去重绝对排第一。很多同学在写“组合总和II”和“全排列II”时，明明用了used数组，也用了startIndex，但结果还是会出现重复的组合或排列。
这里引入两个概念：树枝去重和树层去重。举个例子，假设输入是[1,1,2]，在递归的同一层for循环里，第一个1会生成一系列结果，然后第二个1又会在同一层重新生成这一系列结果，这就是“树层重复”，需要去重。而如果是在同一个分支里连续选了两个1，那是“树枝重复”，这种一般是允许的。
实现树层去重的标准姿势是：先把数组排序，然后在for循环里判断当前元素是否和前一个元素相同，并且前一个元素的used状态是False。
以LeetCode 40 组合总和II为例：
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() result = [] path = [] used = [False] * len(candidates) def backtrack(start, current_sum): if current_sum == target: result.append(path[:]) return for i in range(start, len(candidates)): if i > 0 and candidates[i] == candidates[i-1] and not used[i-1]: continue if current_sum + candidates[i] > target: break used[i] = True path.append(candidates[i]) backtrack(i + 1, current_sum + candidates[i]) path.pop() used[i] = False backtrack(0, 0) return result这个used[i-1]的判断是比较难理解的，我解释一下：在同一个for循环即同一层里，如果前一个相同的元素已经被回溯恢复了（也就是used[i-1]为False），说明它已经把以它为开头的那条路径全部探索完了，那后面的这个相同元素继续探索，就一定是重复结果，所以跳过。但如果used[i-1]是True，说明当前正在同一个递归分支里，前面那个相同元素是父节点，那这第二个相同元素属于树枝上的合法使用，不能跳过。
4.2 用used数组处理集合的去重问题
全排列的去重和组合的去重有一点点区别，因为排列没有startIndex，每一层都会遍历整个数组。所以去重条件里，除了判断前一个相同元素没被使用之外，还要额外判断当前元素本身是否已经用过。
LeetCode 47 全排列II的标准写法：
def permuteUnique(self, nums: List[int]) -> List[List[int]]: nums.sort() result = [] path = [] used = [False] * len(nums) def backtrack(): if len(path) == len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue used[i] = True path.append(nums[i]) backtrack() path.pop() used[i] = False backtrack() return result这套组合拳打下来，你基本就把去重问题搞定了。但说实话，我当年学到这里的时候，这个“not used[i-1]”也是看了很多遍才真正理解，建议你如果第一遍看不懂，直接拿[1,1,2]这个小例子，手动画一下递归树，把每一步used数组的状态写下来，马上就能豁然开朗。
4.3 不用used数组的去重方法：startIndex流派
其实还有一个去重流派，完全不用used数组，而是借助set来实时记录本层已经使用过的元素。思路是：在每一层递归内建一个set，如果当前元素已经在本层出现过，就直接跳过。
这个写法在组合总和II里尤其简洁：
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() result = [] path = [] def backtrack(start, current_sum): if current_sum == target: result.append(path[:]) return used_in_level = set() for i in range(start, len(candidates)): if current_sum + candidates[i] > target: break if candidates[i] in used_in_level: continue used_in_level.add(candidates[i]) path.append(candidates[i]) backtrack(i + 1, current_sum + candidates[i]) path.pop() backtrack(0, 0) return result这种做法的优点是逻辑简单，不需要去理解used[i-1]和used[i]的关系；缺点是要额外开辟set。在数据量很小的时候完全没问题，数据量大的时候，排序加used数组的组合通常更稳。我的写法偏好是：排列去重用used数组，组合去重用used数组，每层set法作为辅助理解。
5. 剪枝优化：从会做题到高效AC的分水岭
5.1 组合问题的经典剪枝：剩余元素不够了就直接停
组合问题的剪枝公式是一个在网上流传很广的公式，很多教程里都有，但讲清楚为什么的人不多。还是以LeetCode 77为例，题目要求从n个数里选k个。我们已经选了path长度个元素，还需要再选k - len(path)个。在for循环里遍历到某个i时，如果i之后剩余的元素个数已经不够补齐所需数量，那以i为开头的所有分支都注定无法凑齐k个数，可以直接break。
具体代码这样写：
for i in range(start, n + 1): if n - i + 1 < k - len(path): break path.append(i) backtrack(i + 1) path.pop()这个剪枝在n=20、k=19这种极限数据下效益极其明显。如果不剪枝，前几层几乎要把所有组合都遍历一遍，剪枝后很多分支在第一层就断掉了。
5.2 求和问题的剪枝：排序加提前break
求和类问题（组合总和、组合总和II）的剪枝核心是排序。只有先排序，才能保证数组的单调性，从而利用“当前元素太大，后面元素更大，直接break”这个逻辑。
剪枝要放在for循环里，不要放在递归入口，因为递归入口的剪枝只是“死亡后拦截”，for循环里的剪枝是“过河前拆桥”。前者省的是递归函数内部继续执行的指令，后者省的是整个递归分支全套调用链的产生。
你可能会问，那求和等于target的时候，递归函数开头的current_sum > target判断还要不要？答案是要，但它是安全性兜底，而不是性能优化。因为在for循环里你已经保证current_sum + candidates[i]不会超过target，正常逻辑下递归进去的current_sum都不会大于target，但出现一些特殊情况时兜底判断能防止死循环。
5.3 棋盘问题的剪枝思路
N皇后这类棋盘问题，是回溯里思想最巧妙的。每一行只放一个皇后，所以递归层数就是棋盘行数，每一层的for循环遍历的是列的位置。剪枝发生在放置皇后前的合法性校验：需要检查同列、两条对角线上是否已经有皇后。
很多初学者会用一个二维数组来记录棋盘上的皇后位置，校验时遍历整个棋盘，这种写法的复杂度很高。提供一个常用优化：用三个数组分别记录“列是否被占用”“主对角线是否被占用”“副对角线是否被占用”，因为主对角线的行+列是定值，副对角线的行-列是定值，用索引直接O(1)查询。
def solveNQueens(self, n: int) -> List[List[str]]: result = [] board = ['.' * n for _ in range(n)] col_used = [False] * n diag1_used = [False] * (2 * n - 1) diag2_used = [False] * (2 * n - 1) def backtrack(row): if row == n: result.append(board[:]) return for col in range(n): diag1 = row + col diag2 = row - col + n - 1 if col_used[col] or diag1_used[diag1] or diag2_used[diag2]: continue col_used[col] = True diag1_used[diag1] = True diag2_used[diag2] = True board[row] = '.' * col + 'Q' + '.' * (n - col - 1) backtrack(row + 1) col_used[col] = False diag1_used[diag1] = False diag2_used[diag2] = False backtrack(0) return result严格来说这叫可行性剪枝，是回溯题里最基础也最必要的剪枝。N皇后如果不用任何剪枝，全排列式的探索会把每种摆法都试一遍，复杂度直接爆炸。
6. 回溯算法的时间复杂度与性能分析
6.1 普通回溯的复杂度估算方法
回溯的时间复杂度通常不是简单的O(N)或者O(N²)，而是和递归树的节点数直接相关。你画一棵递归树，每个节点代表一次递归调用，树的整体节点数乘以每个节点内部的操作成本，就是回溯的总时间复杂度。
拿全排列来说，第一层有N个选择，第二层每个节点有N-1个选择，第三层N-2个选择，最后一共有N!条叶子路径。所以全排列的时间复杂度是O(N!)，空间复杂度是O(N)。组合问题则复杂一些，每个节点的分支数不断递减，总结果数是C(n,k)，整体复杂度可以记为O(C(n,k) * k)。
6.2 剪枝对复杂度的影响
剪枝能优化常数，但一般不改变算法的渐进复杂度阶数。什么意思？就是剪枝后仍然是O(N!)级别的复杂度，但实际的运行时间可能从10秒降到0.5秒，这是数量级的体验差异，在面试笔试里这决定你能不能AC。
所以我的建议是：不要指望通过剪枝把回溯算法从“不可用”变成“可用”，回溯天生适合数据规模很小的场景。在真正的算法比赛中，N大于20你就要考虑是否需要换用动态规划或贪心，而不是硬着头皮写回溯。
6.3 动态规划与回溯怎么选
回溯和动态规划有交集，尤其是“组合总和”这种题，既可以用回溯解，也可以用DP解。区别在于回溯求的是“所有具体方案”，DP求的是“方案数”或“最优值”。如果你的题目要求输出所有解，那就只能回溯；如果只求个数、只求能不能，那就优先考虑DP，因为DP有重叠子问题的优化，而回溯没有。
划重点：看到“所有组合”“所有方案”“所有路径”这三个字，首选回溯；看到“多少种”“最大值”“最小值”“是否存在”，先想DP或者贪心。
7. 刷题路径推荐与实战心法
7.1 按顺序刷完这十道题，回溯基本就通了
我结合自己的刷题经验，给你排一个最适合入门的刷题顺序，每道题都有它独特的技术点，一题一关，打完这些关卡你的回溯水平会有一个质的提升。
- LeetCode 77 组合：学startIndex，这是回溯的基石。
- LeetCode 216 组合总和III：组合加求和剪枝的综合练习。
- LeetCode 17 电话号码的字母组合：把回溯用在映射问题上，锻炼把真实问题建模成组合选择。
- LeetCode 39 组合总和：允许无限重复取同一个元素，学i和i+1的区别。
- LeetCode 40 组合总和II：去重入门，一定要吃透used[i-1]那个判断。
- LeetCode 78 子集：体会“进入节点就收集结果”的思路。
- LeetCode 90 子集II：子集加去重，巩固树层去重。
- LeetCode 46 全排列：从startIndex切换到used数组，体会两种控制方式的不同。
- LeetCode 47 全排列II：去重高阶，排列和去重的双重结合。
- LeetCode 131 分割回文串：切割问题，其实也是组合问题，但需要你做回文判断剪枝。
- LeetCode 51 N皇后：最后的综合大boss，把二维选择和剪枝玩明白。
这道题列表覆盖了组合、排列、子集、切割、棋盘五大题型，每一道做完之后，试着不参考任何答案，自己重新写一遍完整的AC代码，隔一天再写一遍，直到能默写为止。
7.2 实战中的几个致命细节
这部分是纯经验分享，我踩过的坑，不想你在同一处再摔一次。
第一个坑是result.append(path[:]) vs result.append(path)。前面提过，但这里再强调一次。因为Python的列表是引用传递，不拷贝的话result里所有元素都指向同一个path对象，最终回溯结束path变成空列表，result就是N个空列表。解决办法只有一句：永远是path[:]。
第二个坑是递归函数参数里的list做默认值。比如def backtrack(path=[])，这个写法在Python里是一个经典陷阱，因为默认参数在函数定义时就创建并共享，所有递归分支操作的都是同一个列表。至于结果有多惨，你自己试试就会印象深刻。
第三个坑是忘记把used[i]恢复为False。一旦忘记，第一层递归用掉的元素在另一条分支里也被当成用过，直接导致结果少了一大堆排列。每次写完回溯，养成自检习惯，看看“做选择”和“撤销选择”是否成对出现。
第四个坑是在for循环里修改path时不小心用了remove而不是pop。回溯撤销选择时，一定要弹出末尾元素，也就是pop()，而不是按值删除某个元素。按值删除在存在重复元素时会删错对象，逻辑会彻底混乱。
7.3 针对新手学习路线的心法建议
回溯算法的学习曲线确实有些陡峭，但它一旦过了那道坎，之后就全是套路。我辅导过不少刚开始学算法的朋友，发现他们最容易卡住的地方不是不知道怎么写回溯，而是不知道什么时候该用回溯、什么时候该用DP。
给你一个非常粗暴但有效的判断法：题目里的数据范围n小于等于15到20左右，并且要求列出所有符合条件的方案，那大概率是回溯。因为20!已经是一个天文数字，但剪枝后的回溯勉强可以跑出结果；而如果n已经到了100、1000，还要列所有方案，那你得想想是不是题意理解错了，可能只是让你输出方案数，这时候回溯就不合适了。
另外，学回溯时一定要亲手画递归树，不要只在脑子里想象。画递归树的目的不是为了让别人看懂，而是让你自己能直观地看到“什么时候产生了重复”“剪枝应该落在哪一层”。我当年学全排列II的时候，手动画了满三层的递归树，用红笔圈出所有重复分支，写完这个之后，之后所有去重题我都没再出过错。
8. 总结的经验：如何彻底吃透回溯算法的套路与变形
回溯的一大特点是变着花样出题，但剥开外壳，里子永远是那三块：递归、选择、撤销。今天我把组合、排列、子集、切割、棋盘五类问题全部归类了一遍，你会发现它们的解法代码长得几乎一样，区别只在startIndex、used数组、去重条件、终止条件这几处参数上。
如果你现在已经能独立写出组合和全排列这两道题，恭喜你，回溯已经算入门了。接下来要做的不是盲目刷更多的新题，而是把做过的题目多做几遍，用不同的写法（比如把used数组改成set，或者把递归改成迭代）去重写同一道题，体会不同写法之间的等价关系和性能差异。
还有一个小习惯我留着最后说：每次刷回溯题时，都会在代码注释里写出对应题目的“递归树结构”和“状态变量含义”。等注释写多了，你会发现自己看一眼题目就知道该定义哪些变量了，这种直觉才是刷题真正的核心竞争力。回溯可以难，也可以很简单，区别只在于，你是否真正理解了那一次次的“反悔”。
