很多人刷力扣hot100的时候前面链表、二叉树、动态规划都还能咬牙坚持一到回溯算法这个专题突然就卡住了。明明看题解每行都认识自己一写就各种不对要么结果重复要么死循环要么根本不知道递归函数要传哪些参数。其实回溯算法没这么玄乎它本质上就是“在递归树上做深度优先遍历走不通就回头”。hot100里的回溯题虽然看起来题型五花八门——组合、排列、子集、棋盘、括号生成、单词搜索——但剥开外壳全是同一套骨架。这篇文章我把hot100回溯专题的通用套路、每类题型的破解思路、剪枝技巧和踩过的坑一次讲清楚希望能帮正在刷题的你真正拿下这一类题。1. 回溯算法为什么是hot100里的“硬骨头”1.1 所有回溯题都在做同一件事先说一个很多人没想明白的点回溯到底在解决什么问题一句话总结回溯解决的是“枚举所有可能性”的问题只不过它枚举的时候不是傻傻地全列出来而是用递归的方式逐层构造解并在中途发现某个分支不可能得到合法结果时及时止损掉头换一条路走。你可能听过“回溯 深度优先搜索 状态恢复”这种说法确实是这样。但更直观的理解方式是回溯其实是在遍历一棵“决策树”。树的每一层对应解中的一个位置每个节点代表一个选择。比如组合问题里你决定第一个数选谁、第二个数选谁排列问题里你决定第1位放哪个元素、第2位放哪个元素N皇后问题里你决定每一行皇后放在哪一列。遍历完整棵树所有叶子节点或者经过剪枝存活的叶子就是所有合法解。所以回溯题再怎么变核心代码结构永远是“递归 循环”两层嵌套循环负责横向遍历当前层的所有选择递归负责纵向往下一层走。入门的时候把这个心智模型建立起来后面再难的题也跑不出这个框架。1.2 从一棵最小回溯树理解回溯的本质我用hot100里最简单的一道题——力扣78题“子集”来演示这棵树长什么样。输入[1,2,3]要求输出所有子集。标准回溯解法是def subsets(nums): res [] path [] def dfs(start): res.append(path[:]) # 每个节点都收集 for i in range(start, len(nums)): path.append(nums[i]) dfs(i 1) path.pop() # 撤销选择 dfs(0) return res这里为什么res.append(path[:])要加一个[:]为什么递归结束要path.pop()是新手最容易懵的两个点。先说path[:]Python里列表是引用类型如果你直接res.append(path)后面path一变之前存进去的结果也跟着变最后得到一堆空列表。所以必须拷贝一份快照。再说path.pop()这是回溯的灵魂——你选择了1往下走把所有以1开头的子集收集完之后必须把1从路径里弹出来这样才能轮到2开头。如果你不撤销路径只会越加越长完全乱套。整个递归过程其实就是在做“选了1之后能构成哪些子集然后再也不选1去选2”。所以回溯看起来是在“后悔”但它不是无能而是故意保留后悔的机会——每次只做一步决定走完立刻回到上一步重新选这样才能不重不漏地覆盖所有分支。2. 一模板走天下回溯题目的通用骨架2.1 核心模板代码把hot100所有回溯题过一遍就知道不管题面怎么变代码都是同一个模板。我通常这样写def backtrack(参数列表): if 满足终止条件: 收集结果 return for 选择 in 当前层的选择列表: 剪枝条件(如果提前知道这条路不行) 做选择 backtrack(新的参数) # 递归进入下一层 撤销选择这个模板细化到每一道题只需要回答三个问题“参数列表”里要传什么一般是当前搜索的位置startIndex、已选择的路径状态、以及题目给出的原始数据。“终止条件”是什么组合、排列问题是搜索到足够长度子集问题是每个节点都收集N皇后是放满最后一行。“当前层的选择列表”是什么组合/子集问题是从 startIndex 开始遍历排列问题是遍历所有还没用过的元素棋盘类问题是遍历当前行的所有列。把这三个问题弄清楚一道回溯题就变成填空题了。2.2 模板里每个参数为什么这么设计很多人在写回溯时卡在“不知道递归函数应该传哪些参数”。这里我给一个比较实用的判断标准凡是递归到下一层时会发生变化的状态都得作为参数传下去凡是全局不变的数据放在外层引用即可。比如组合总和那道题candidates数组是不变的没必要每次递归都传一份拷贝但start下一次从哪个位置开始选和path当前已经选了哪些数是变化的必须传。再比如全排列used数组用来记录哪些元素已经被选了它虽然是一个引用类型可以被所有递归层共享但你传它和不传它在功能上没区别——因为关键是要在每层递归里看到最新的used状态所以通常也放在闭包外层而不是当成普通值参数复制一份。如果你喜欢C写回溯要注意一个非常经典的坑vectorint path作为递归参数时如果按值传递每次递归都会发生拷贝虽然逻辑对但很慢所以一般用引用或者全局变量配合push_back和pop_back。Python因为列表本来就是引用传递天然适合写回溯这也是我推荐用Python刷回溯题的原因。2.3 什么时候需要撤销操作撤销操作不是可选项是回溯的必要组成部分。但有些题你会发现网上代码里撤销操作好像被“藏”起来了。最典型的是“括号生成”这种题如果用的是字符串拼接的方式比如backtrack(s ()那确实不需要显式撤销因为字符串是不可变的s (会产生一个全新的对象原来的s没变递归回来自然就是“撤销”状态。但如果你用列表保存路径比如path.append(...)再backtrack(...)那必须path.pop()因为列表是可变对象你不手动撤销路径内容就残留了。这里有个判断口诀用了可变对象列表、数组就必须手动撤销用了不可变对象字符串、整数可以通过传新值自动撤销。这个点看着小实际写代码时特别容易出 bug我见过不少人用列表存路径却忘了 pop结果死循环或者结果暴涨。3. hot100里三类必考回溯题的拆解思路3.1 组合类从组合总和系列理解 startIndexhot100里的组合题主要有“电话号码的字母组合”“组合总和”“组合总和II”这几道。组合问题的共同点是选过的元素不能再选同一分支内不同顺序不重复算。那怎么避免[1,2]和[2,1]重复靠的就是startIndex。每次递归时下一层从i 1开始而不是从0开始。这样你选了1之后后面只能在2、3里选选了2之后后面只能在3里选。相当于把决策树从左到右推进天然避免回头也就避免重复。组合总和II比组合总和难一点因为输入数组里有重复元素同时每个数字只能用一次。这时候光靠 startIndex 不够还要排序后做同层去重。这个放到第4章的剪枝部分详细讲这里先记住结论看到“结果不能包含重复组合”就去想排序 相邻去重看到“每个元素只能使用一次”就用 startIndex 1 往下走。3.2 排列类全排列系列里的 used 数组全排列和组合最大的区别是排列里元素的顺序是敏感的[1,2]和[2,1]是两个不同结果所以每层递归都可以从数组头部开始选择但在一个具体分支里同一个元素不能被用两次。怎么判断元素是否被用过用一个used布尔数组。全排列的基础版写法是这样的def permute(nums): res [] used [False] * len(nums) def backtrack(path): 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) path.pop() used[i] False backtrack([]) return res你注意这里没有 startIndex因为排列允许每个位置从任何元素开始选但有used来保证同一分支内元素不重复。组合靠 startIndex 控制方向排列靠 used 控制占用这就是两种题最核心的代码差异。全排列II加了重复元素比如[1,1,2]要求不能有重复排列。这时除了used之外还要排序 同层去重。同层去重的标准判断是i 0 and nums[i] nums[i-1] and not used[i-1]然后直接continue。这个条件背下来没什么用你得理解它到底在防什么——防止在同一层选择列表里用了值相等的两个不同元素。3.3 棋盘/地图类N皇后与单词搜索N皇后和单词搜索是hot100回溯题里的“压轴题”但它们同样没有跳出模板。N皇后每一层递归处理一行循环尝试每一列判断当前位置能不能放皇后能放就放然后递归下一行递归返回后撤销。判断能不能放皇后的时候只需要检查当前列、左上对角线和右上对角线有没有已经放过的皇后不需要检查左下和右下因为你是从上往下按行放置的下面还没有皇后。单词搜索稍微有点特殊因为它的“递归树”是二维网格每次可以向上下左右四个方向走。这里除了用回溯模板还得注意进入一个格子后要标记它已经访问过防止同一条路径上走回头路递归完再恢复标记。你可以单独建一个visited数组也可以原地把格子改成特殊字符再改回来后者更省空间。4. 剪枝的正确姿势从TLE到AC的优化链路4.1 剪枝本质砍掉不可能的分支回溯虽然能枚举所有可能性但如果不做任何优化指数级甚至阶乘级的搜索树分分钟让你超时。剪枝就是在递归过程中提前发现某个分支不可能产生合法结果或不可能产生最优解直接放弃进入这条分支。它不影响正确性只影响效率。hot100里的剪枝大致分两类一类是去重剪枝砍掉会生成重复结果的分支另一类是可行性剪枝砍掉明显不可能走到答案的分支。4.2 去重剪枝排序 同层去重去重剪枝最常见的两个场景就是“组合总和II”和“全排列II”。以组合总和II为例输入[10,1,2,7,6,1,5]数组里有重复的1如果不去重你会得到两组[1,2,5]、[1,7]这种重复结果。去重的关键手段是先排序然后在同一层循环里跳过和前一个元素相等的元素。代码就一行if i start and candidates[i] candidates[i-1]: continue为什么条件是i start而不是i 0因为i start才表示“同一层”的重复。如果写i 0会把不同层的两个相同值也跳过导致结果漏项。这个细节我当时踩过坑因为candidates [1,1,2]这种输入里你允许第一个分支选index0的1第二个分支选index1的1但如果用i 0去判断index1的1任何时候都会被跳过正确结果[1,2]就永远出不来了。所以记住同层去重的判断边界是“当前层起始位置 start”不是数组头。排列问题的去重稍微复杂一点因为每层都从0开始遍历你要区分“同一个分支内别用同一个元素”和“同一层内别用相等的元素”两者都靠used数组。写法是这样if used[i]: continue if i 0 and nums[i] nums[i-1] and not used[i-1]: continue used[i] True第二个条件的not used[i-1]是什么意思它表示前一个相等的元素在当前分支里没用过那说明当前元素和它是在同一层做选择直接用当前元素会产生和之前一样的排列所以要跳过。反过来如果used[i-1]是 True说明前一个相等的元素已经在当前路径上这时允许当前元素继续选因为这是“同一分支内”的重复元素不是同层重复。4.3 可行性剪枝充分利用题目限制条件可行性剪枝是根据题目具体条件提前终止。比如“组合总和III”里要找和为n的k个数如果当前和已经大于n后面再加只会更大直接return“组合总和”里可以先排序当target - candidates[i] 0时因为数组有序后面更大的元素更不可能直接 break 掉整个for循环。再比如N皇后判断当前格子能不能放皇后的过程本身就是一种剪枝——把一个分支在进入下一层之前就过滤掉。is_valid函数写得对不对直接决定N皇后这道题跑得快不快、甚至能不能跑完。还有一个容易忽略的可行性剪枝在“分割回文串”里每次截取一段子串之前可以先判断它是不是回文串不是就直接continue不必把非回文串塞进递归路径再回头发现不行。这个判断虽然只省了一层递归但在字符串长度较大时效果很明显。5. 回溯的复杂度与状态管理面试追问怎么答5.1 时间复杂度和空间复杂度怎么估算回溯的复杂度不能像二分、双指针那样直接给出一个简单公式它取决于递归树的节点数。刷题和面试时通常这样估算组合/子集类问题每个元素有选或不选两种状态枚举所有子集是O(2^n)。如果每个合法结果还要拷贝到结果集拷贝成本是O(n)所以总复杂度是O(n * 2^n)。排列类问题第一层有n种选择第二层有n-1种总节点数是n!级别。每收集一个排列还要O(n)拷贝所以是O(n * n!)。N皇后每一行尝试n列但每一行放置后都会排除一些列总状态数接近O(n!)。判定冲突如果每次用循环扫描还要再乘一个O(n)所以实际是O(n * n!)。空间复杂度相对简单主要是递归调用栈的深度和路径数组的长度。组合、子集、排列的递归深度是O(n)N皇后的递归深度是O(n)所以空间复杂度都是O(n)不考虑结果集本身占用的空间。有些题用 visited 数组记录访问状态也是O(n)。面试时能把这几个公式推导清楚比死记硬背强很多。5.2 状态管理的三种手段回溯里说的“状态”无非就是当前已经选了哪些元素、当前处于什么位置、哪些元素被占用。hot100题里常见的管理手段有三种startIndex只记录“从哪个位置开始”用于组合、子集题保证组合不重复。used数组记录“哪些元素被用过”用于排列题以及需要去重的场景保证同一分支内元素不重复。回溯现场恢复用路径数组保存选择时恢复操作就是path.pop()用字符串拼接时不需要恢复修改全局 visited 标记后递归返回时需要还原。这三者经常组合出现。比如全排列II同时用了 used 数组和回溯现场恢复组合总和II同时用了 startIndex 和排序去重。面试官问你“这个题的状态是怎么流转的”你就按这三个维度回答基本不会乱。6. 回溯高频易错点复盘我踩过的坑6.1 Python引用的坑结果集被掏空我第一次写子集题的时候res.append(path)最后拿到的是十几个空列表。原因前面提过Python列表是引用append进去的是path这个对象的引用不是快照。后来我养成习惯所有递归类题目收集结果一律写path[:]或者list(path)。C里类似如果你std::vector是全局的那就必须在加入结果时拷贝一份通常写成res.push_back(path)反而是拷贝因为按值push会复制但要注意如果你不小心写成res.push_back(std::move(path))后面 path 就废了。语言不同坑的方式不同本质都是一回事别把可变对象的引用留到结果集里。6.2 去重忘了排序组合总和II那种“数组有重复元素但结果不能重复”的题目去重的前提是排序。我第一次刷的时候没排序就套用candidates[i] candidates[i-1]去重结果发现两个相同的1隔着老远去重条件根本触发不了结果照样重复。后来意识到去重剪枝依赖相邻重复元素的判断而相邻的前提是排序。所以遇到“有重复元素 结果去重”的题第一步永远是sort不是写回溯函数。6.3 剪枝位置写错导致结果缺失有一类错误是剪枝条件位置放得太早。比如组合求和里当前remain target - sum(path)如果remain 0确实不用再递归了。但如果你在 for 循环之外做一个if remain 0: return有些情况下会漏掉当前层的其他选择。正确的剪枝位置要么放在 for 循环内、每次选择之后判断要么在进入递归之前判断。位置不对不会报错但结果会莫名其妙少几组这种 bug 特别难查因为不是语法错误。我的处理方式是剪枝条件紧贴着“做选择”的代码写让它和选择动作绑定不要单独放一层。6.4 N皇后坐标计算里的对角线陷阱N皇后里判断对角线冲突最容易算错的是主对角线和副对角线索引。我用按行放皇后的方法当前要放在第 row 行第 col 列检查之前的第 r 行第 c 列。主对角线冲突条件是row - col r - c副对角线冲突条件是row col r c。如果你用二维 bool 数组记录占用的对角线要注意数组下标不能为负所以主对角线索引一般写成row - col n来平移。这个细节不写对N皇后检查永远通过不了或者永远不许放子。7. hot100回溯题的推荐刷题顺序7.1 三阶段刷题路径hot100里的回溯题大概有17、22、39、40、46、47、51、78、90、79、131这11道左右。很多人拿到hot100就从头刷到尾到回溯这块碰壁后容易放弃。我建议按三阶段走第一阶段建立框架17、78、46、22力扣78子集理解“每个节点都收集”的模板。力扣46全排列理解 used 数组和排列题的逻辑。力扣17电话号码的字母组合练一练从多个集合里取元素的回溯。力扣22括号生成理解“选择列表”不是固定的数组而是左右括号的数量条件。第二阶段处理重复90、40、47力扣90子集II排序 同层去重。力扣40组合总和II去重 可行性剪枝。力扣47全排列IIused 数组和同层去重结合是这块难度的一个小高峰。第三阶段综合应用131、79、51力扣131分割回文串回溯 回文判断理解“选择”可以是子串。力扣79单词搜索二维网格上的回溯 visited 管理。力扣51N皇后回溯 合法性校验的综合运用适合作为收官。7.2 每道题的核心考点题目核心考点需要特别理解的点78 子集基础模板所有节点都收集结果46 全排列used 数组排列不含重复排列17 电话号码字母组合多集合回溯每层选择列表不同22 括号生成选择条件控制右括号数量不能超过左括号90 子集II排序 去重同层去重条件40 组合总和II去重 剪枝startIndex 和同层去重配合47 全排列II两层去重used 前值判断131 分割回文串子串作为选择回文判断时机79 单词搜索网格回溯访问标记与恢复51 N皇后合法性判断对角线坐标计算我个人在实际刷题中体会比较深的一点是回溯题不要贪多把上面这11道题每一道都至少独立写两遍第一遍照着模板套第二遍尝试不看模板自己推导参数和终止条件。写完之后再做类似的新题基本看一眼就知道该用 startIndex 还是 used该在哪个位置剪枝。还有一个小技巧写回溯时把递归函数单独抽出来参数命名清楚比如 start 和 used 这种测试的时候打印一下 path 的变化过程很多位置错误一眼就能看出来。等这一步过了回头再看hot100动态规划那部分你会发现思维模型其实是有相通之处的——都是在一棵树上做状态转移只不过回溯是“显式地搜”DP是“隐式地推”。