第一次见到回溯题的时候我整整一个下午没缓过来。题目是全排列第一反应是三层循环套上去结果输入一变长的就崩了后来知道标准做法只用递归满打满算十几行代码。奇怪的是代码我可以默写出来但稍微换个题就不会了——组合还好子集也行一上N皇后直接傻眼。当时我还没意识到回溯真正的门槛根本不在代码而在“你怎么看待这棵树”。这就是标题里“算法学习day25-回溯”的含金量。第25天刚好是我刷题计划中从“会背模板”到“会设计状态”的分水岭回溯是什么、怎么剪枝、怎么去重、复杂度怎么算几乎全在这几天里被打通了。这篇文章不打算从高深的理论讲起而是把我自己踩过的坑、用顺手的写法、以及从全排列到数独的完整推导路径全部整理出来。适合刚吃透递归、正准备啃回溯的读者也适合刷过一批回溯题但总觉得差了点什么的朋友。1. 回溯到底是什么从走迷宫到解空间树1.1 一个所有人都走过的直觉模型回溯的“回溯”两个字本身就来自走迷宫。你在一个岔路口选了一条路走了一段发现是死胡同于是退回到刚才的岔路口换一条路再试。电脑干的事和这个一模一样只不过它把“岔路口”建模成了递归中的每一次调用把“试路”建模成了循环里的每一个选择。最容易被忽略的一件事是回溯不是某种新的算法套路它就是在状态空间树上做深度优先遍历只不过在遍历的过程中必须带着“撤销”这个动作。走迷宫时你没有把走过的路从地图上抹掉是因为地图是固定的但在算法题里如果你试了1这条分支回到分岔点时却不把1从路径里拿掉那下一条分支就会变成1,2、1,3而不是干净的2、3。所有写错的回溯代码十有八九都是忘了这一步。我后来特别喜欢用“试螺丝刀”来类比你面前有一把锁手里有六把看起来差不多的螺丝刀你得一把一把试试完一把就放回原位再拿另一把。放回原位就是回溯里的撤销操作。代码里对应的动作是path.pop()是used[i] False这两个操作少一个整棵树就被污染了。1.2 解空间树一眼看穿递归在干什么如果你把一次回溯算法的完整执行过程画出来会得到一棵树。树的根是空状态每个节点是一次递归调用节点下面挂着当前层可做的所有选择。拿全排列举例nums [1,2,3]时根节点路径为空第一层可以选择1、2、3生成3个分支第二层选择1之后下一层只能选2、3选择2之后下一层只能选1、3第三层填满3个位置到达叶子记录结果这棵树就是“解空间树”。理解了这棵树你就理解了回溯里几乎所有术语递归的深度等于路径长度for循环是在枚举当前层的孩子used数组和startIndex是在决定当前层能选哪些孩子剪枝是发现某个孩子下面不可能有答案时直接不往那边走去重是发现两个孩子长成一样于是只留一个。我在第25天之前一直不懂“回溯 深度优先搜索”这句话。总觉得DFS是图算法回溯是数学题。后来才想明白图里的DFS遍历的是图结构回溯遍历的是“解状态”组成的虚拟树。两者代码骨架几乎完全一样只是回溯在每个节点上多了记录和撤销的步骤。这么一对应之后学记忆化搜索、学状态压缩全都是顺水推舟的事。1.3 回溯和暴力枚举的边界在哪里有人问回溯不就是暴力吗把每个组合都枚举一遍复杂度还不是指数级这么说对也不对。暴力枚举意味着你提前知道要嵌套几层循环比如“三个数里选组合”你写三层循环“四个数”写四层。可一旦n变成变量循环层数写不出来暴力枚举直接失效。回溯用递归来代替循环层数本质上是用递归的栈深度去模拟那个不确定的嵌套层数。这个能力让回溯能处理n不固定、约束复杂、必须边走边判断的题目比如N皇后、数独、括号生成。所以更准确地说回溯是系统化的暴力枚举它把“枚举”这件事做成了可伸缩的模板。代价是时间复杂度仍然很糟糕所以才需要下一章严格训练的剪枝和去重。没有剪枝的回溯几乎是不可用的这是所有从模板入门回溯的人迟早会撞上的墙。2. 回溯模板与入门三件套全排列、组合、子集2.1 统一模板选择-递归-撤销三步曲回溯题不管怎么换皮代码骨架都是同一个。我现在的习惯是先写出这个模板再把具体题目的状态、出口、剪枝条件填进去def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 当前可做的所有选择: 做选择更新路径和状态 backtrack(路径, 新的选择列表) 撤销选择恢复路径和状态用伪代码写出来只有四行但其中“记录结果”和“撤销选择”这两步最容易翻车。记录结果时Python里如果你写res.append(path)之后path一变res里存的东西也跟着变——因为path是同一个列表对象。必须写成res.append(path[:])做浅拷贝或者存一个拼接好的字符串。至于撤销选择第五章我会专门列一个避坑清单。这个模板真正重要的地方在于你必须明确“路径”、“选择列表”、“结束条件”三样东西分别是什么。全排列的选择列表是“所有还没被用过的元素”组合的选择列表是“当前下标之后的所有元素”子集的选择列表则是“当前下标之后的所有元素且在每一层都记录当前路径”。三句话就能看出它们之间的差异在哪里。2.2 全排列用used管理“还能选谁”全排列是最适合入门的回溯题因为它的状态定义最直白路径就是一个排列路径长度等于数组长度时结束选择列表是“还没放进路径里的元素”。def permute(nums): res, path [], [] used [False] * len(nums) def dfs(): 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]) dfs() path.pop() used[i] False dfs() return res这里used数组就是“选择列表”的落地实现。它记录的是“下标是否被占用”而不是“值是否被用过”——这个区别在有重复元素的排列里会变得极其关键第四章再展开。递归结束后used[i] False被称为“回溯”的经典动作千万别漏。可以用一个临时数组验证把这个赋值注释掉结果会变成什么呢输出会非常离谱同一层的每个分支都会沿用上一分支用过的元素最终路径长度暴涨递归永不结束或结果疯狂重复。2.3 组合和子集startIndex承担了什么角色组合题combine(n, k)让你在1到n里选k个数不考虑顺序。如果不做任何限制[1,2]和[2,1]会同时出现但那在组合语义下是同一个东西。解法是用一个start参数规定下一层只能从i1开始取数这就叫“不回头”——后面的选择不能在它前面再选。def combine(n, k): res, path [], [] def dfs(start): if len(path) k: res.append(path[:]) return for i in range(start, n 1): path.append(i) dfs(i 1) path.pop() dfs(1) return res子集题则是组合的变体所有长度的组合都要。所以它不在叶子才记录而是在每个节点都记录当前路径。另一种理解是把“选或不选每个元素”展开成二叉树每次递归可以走两条路选当前元素或不选。但用start版本的写法更统一代码也更紧凑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 res2.4 三者的状态与出口差异对照把三道题放在一起对比表格比文字直观得多题型结束条件下一层起始位置记录时机核心状态子集不设出口自然遍历完成i1每个节点start组合路径长度等于ki1叶子节点start排列路径长度等于n无下标概念用used过滤叶子节点used这张表我每次做回溯题都会在心里默念一遍。题目一变先判断它是排列还是组合还是子集再决定用used还是start。把两者混用是目前刷题社区里最常见的错误有人写组合却在递归里从头循环结果同一组合出现多次有人写排列却传了个start结果能选的元素越来越少答案直接少了一大半。3. 剪枝回溯从“能跑”到“跑得动”的关键3.1 剪枝的本质提前砍掉必死的子树回溯的时间复杂度天然是指数级的。全排列n!、子集2^n当n稍微大一点不剪枝的版本会慢得让人怀疑人生。剪枝要做的事很简单在遇到某个节点时如果能判断出这个节点下面的所有分支都不可能产生合法答案就不进入这些分支。相当于走迷宫时你看到地上标着“此路不通”于是连试都不想试直接换路。但这里有个容易误解的点剪枝的前提是你有足够的判断能力。判断能力来自题目约束。比如组合总和的题combinationSum目标值target如果当前累加的和已经超过target那么继续往下加正整数只会更大可以整体放弃比如N皇后如果某列已经放了皇后那这一列的所有格子都不用再试。判断不了的分支只能老老实实走完。3.2 两类常见剪枝约束剪枝与限界剪枝第一类是约束剪枝本质是“不合法就不走”。第二类是限界剪枝本质是“即使能走到底也没有继续的价值”。我把它们分开记是因为写代码时它们的表现形式不同约束剪枝一般写在for循环里作continue条件限界剪枝一般配合排序作break。拿组合总和I来展示限界剪枝def combinationSum(candidates, target): res, path [], [] candidates.sort() def dfs(start, cur_sum): if cur_sum target: res.append(path[:]) return for i in range(start, len(candidates)): # 剪枝candidates升序后边的更大不需要再试 if candidates[i] target - cur_sum: break path.append(candidates[i]) dfs(i, cur_sum candidates[i]) path.pop() dfs(0, 0) return res这里排序是剪枝的前提。没有排序你没法确定后面元素都大于当前元素自然不能用break提前结束整层循环。这是很多教程不会单独提醒的细节限界剪枝常常和排序绑定出现把排序写在递归外面的原因就在这里。顺序写反了剪枝条件不仅不成立还会把正确答案直接剪掉程序还不报错调试起来特别难受。3.3 剪枝翻车实录我把合法解剪掉了剪枝写错方向这件事我亲身经历过一次。当时写N皇后检查列和对角线的代码是if cols[col] or diag1[row col]: continue漏掉了副对角线diag2[n - 1 row - col]。结果程序跑得飞快答案数量却比正常的n4少了两套。功能缺失完全不报错只有把答案和标准输出对比才能发现。更隐蔽的是另一种错误把对角线索引公式的边界算错导致某些列明明合法却被当成冲突跳过。这种问题没有任何报错纯粹是逻辑层面错了。从那以后我养成了两个习惯。第一个是写剪枝时一定先画一个最小样例的状态树把剪枝条件的每一步对着题目的约束逐条过一遍。第二个是默认相信自己会写错写完就用最朴素的暴力解跑一遍小数据做对拍。回溯题的剪枝是加分项但前提是功能必须正确。先保证不剪枝版本能得出正确答案再加剪枝优化这个顺序不能反过来。4. 去重陷阱为什么答案里会出现重复项4.1 重复的两个来源去重是整个回溯里最绕的部分因为它要区分两种完全不同的“重复”。第一种是顺序层面的重复。组合题里[1,2]和[2,1]是同一个答案这个用startIndex解决前面已经提到。第二种是相同值的重复。输入数组nums [1, 1, 2]时元素是有相同的。如果还按普通排列去写两个1都会被当成独立的可选项于是[1_1, 2]和[1_2, 2]会同时出现在结果里——它们位置不同、语义不同但在人眼里都是[1, 2]。题目要求去重的话就要决定这两个1在同一层只能被选一次。很多初学者会把这两种重复混为一谈一看到“去重”就在结果里加set那是下策。真正清晰的思路是先想清楚重复来自同一路径的不同顺序还是来自同一数值被当成不同元素。前者用startIndex后者用排序加used数组。4.2 三种去重方案的功能对比假设题目是“有重复元素的排列输出不重复的排列”常见有三种处理方式方案思路优点缺点结果事后去重生成全部排列排序后去重代码改动小先白跑一遍重复分支数量和开销都很大每层集合去重在for循环里用local_used记录本层已选值直白不用排序每次递归都新建集合内存和常数开销大排序used跳层数组排序后同层遇到相同值跳过剪枝彻底性能好需要理解used[i-1]状态第三种是我推荐的方案。它能避免大量无效递归在n较大时优势明显。代码长这样def permuteUnique(nums): res, path [], [] nums.sort() used [False] * len(nums) def dfs(): if len(path) len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue # 关键去重同一层相同值前一个已经回溯完used[i-1]为False if i 0 and nums[i] nums[i-1] and not used[i-1]: continue used[i] True path.append(nums[i]) dfs() path.pop() used[i] False dfs() return res4.3 排序去重的核心细节为什么是not used[i-1]上面这行去重判断是整个回溯里最容易被写反的一行。许多人背下来代码却没搞懂为什么是not used[i-1]而不是used[i-1]。关键在于nums[i] nums[i-1]意味着当前这个值和前一个值相等。现在分叉成两种情况。如果used[i-1] True说明前一个相同的值还在当前这条路径上比如路径已经选过第一个1现在要选第二个1这是合法的、正常的树枝上的连续选择。如果这时候把分支剪掉[1, 1, 2]这种答案永远出不来。如果used[i-1] False说明前一个相同的值已经被用过又被撤销了。这意味着上一棵子树已经完全走完现在回到了同一层的下一个兄弟节点。此时再选这个相同的值就会生成和上一棵子树一模一样的路径。这才是应该剪掉的情况。所以判断条件必须是“前一个相同值不在当前路径上时跳过当前值”。用not used[i-1]表达的就是这个语义。这个细节也是面试或文档里高频出现的追问点。理解它之后所有排序去重题都能无障碍套用。5. 从模板到实战N皇后、数独和更复杂的状态设计5.1 N皇后一维路径装不下二维棋盘全排列、组合、子集这三件套练熟之后我一度以为回溯没什么大不了。N皇后直接把我打回原形——因为它的路径不再是一个简单列表而是一个棋盘递归的每一层也不再对应“选择列表里的一个下标”而是对应棋盘的一行。我推荐的写法是按行递归。一行放一个皇后递归函数传入当前行号row在for col in range(n)里尝试当前行的每个列位置。只要能通过列、主对角线、副对角线三个约束检查就把皇后放下再进入row 1。这样做的好处是递归深度固定等于n每一层只负责一行状态记录也只剩三个额外数组def solveNQueens(n): res, board [], [[.] * n for _ in range(n)] cols [False] * n diag1 [False] * (2 * n - 1) # 主对角线 row col 范围 0..2n-2 diag2 [False] * (2 * n - 1) # 副对角线 n - 1 row - col def dfs(row): if row n: res.append([.join(r) for r in board]) return for col in range(n): if cols[col] or diag1[row col] or diag2[n - 1 row - col]: continue cols[col] diag1[row col] diag2[n - 1 row - col] True board[row][col] Q dfs(row 1) board[row][col] . cols[col] diag1[row col] diag2[n - 1 row - col] False dfs(0) return resN皇后教我的最重要一课是回溯的状态不一定只有一个列表它可以是多个并行状态。路径是棋盘状态是三个布尔数组两者要一起“做选择”和“撤销”。很多难一点的回溯题都是这个模式——比如数独需要维护行、列、宫三组集合本质完全一样。5.2 数独找到第一个空格直接开搜的写法数独比N皇后更接近“搜索”的原始形态因为它不是一行一行往下填而是需要不断跳转到下一个空格。一种简单稳定的写法是每层递归用双重循环找到第一个空格再尝试填入1到9的所有数字填完继续递归如果所有数字都试过还是不行就返回上一层把当前数字清掉。这里要特别注意的是数独的“剪枝”不是锦上添花而是正确性的一部分只有当前数字不冲突才允许继续往下填。用集合记录行、列、宫内已有数字冲突检查就变成三个in判断def solveSudoku(board): rows [set() for _ in range(9)] cols [set() for _ in range(9)] boxes [set() for _ in range(9)] for r in range(9): for c in range(9): if board[r][c] ! .: v board[r][c] rows[r].add(v) cols[c].add(v) boxes[r // 3 * 3 c // 3].add(v) def dfs(): for r in range(9): for c in range(9): if board[r][c] .: b r // 3 * 3 c // 3 for num in map(str, range(1, 10)): if num not in rows[r] and num not in cols[c] and num not in boxes[b]: board[r][c] num rows[r].add(num) cols[c].add(num) boxes[b].add(num) if dfs(): return True board[r][c] . rows[r].discard(num) cols[c].discard(num) boxes[b].discard(num) return False return True dfs()这种层层跳到第一个空格的做法代码量不多但对“状态撤销”的要求更高三个集合里加了什么递归返回后就要立刻删掉。用discard而不是remove是我个人的习惯虽然这里添加后必然存在但写成discard能避免撤销顺序搞错时直接抛异常调试时少一点崩溃。5.3 回溯的“亲戚”记忆化搜索与动态规划刷到第五周时我开始遇到一些“长得像回溯”却不能用回溯硬莽的题。比如某个状态在递归中会被反复计算很多次明明同一个子问题已经算过回溯还是会重算一遍。这种题的正确解往往是记忆化搜索在回溯的入口接收一个memo字典计算过某个状态就直接返回缓存结果。一个典型的场景是“从起点到终点的路径数量”。第一个版本我用回溯枚举所有路径n稍微大一点就超时。后来改成memo[(i, j)] dfs(i, j)的形式几十行代码变成几行运行时间从指数级降到线性。这件事给我的启发是回溯不只是一个个独立题型的代称它是一种搜索范式。理解了这个范式之后记忆化、动态规划这些优化手段自然都能接上——你只是不再从零开始设计“怎么枚举”而是先枚举再想办法避免重复枚举。6. 复杂度与性能优化心里有数才能不慌6.1 时间复杂度到底该怎么估回溯题面试必问复杂度但很多人的回答是笼统的一句“指数级”。更专业的说法是全排列结果数是n!每个结果拷贝路径要O(n)总时间O(n * n!)组合结果数是C(n, k)每个结果也是O(k)总时间O(k * C(n, k))子集结果数是2^n每个结果拷贝要O(n)总时间O(n * 2^n)一句话总结就是答案个数乘以生成每个答案的平均成本。剪枝可以让这个上界在实际数据上变小但理论分析通常还是按未被剪枝的情况来写。N皇后更特殊一些经典回溯的上界是O(n!)实际因为列和对角线的剪枝跑得远比这个上界快但面试里给出O(n!)并说明剪枝影响即可。6.2 空间复杂度递归深度和结果集分开看空间复杂度有两个大头。一个是递归时正在使用的那条路径占O(递归深度)另一个是最终存下的所有结果占O(答案数 * 答案长度)。如果把所有答案都存在内存里空间往往就比时间更吓人——全排列的n10时结果数组就有几百万项。有些题目只要求输出答案数量那就不要在递归里逐步append到全局列表而是用一个计数器累加空间立刻降到O(n)。6.3 实际优化时应该按什么顺序做我个人的优化顺序是先验证正确性再考虑剪枝最后才碰常量优化。具体手段从易到难大概是排序后结合限界条件提前break这是性价比最高的一步检查能否用set或布尔数组代替in list避免每次选择都遍历在状态设计上压缩比如N皇后用位运算标记列和对角线比布尔数组再快一个常数级约束条件多的题可以加启发式比如数独里优先填“可选数字最少”的空格这是MRV策略代码会复杂一些但速度提升非常明显记住一个反直觉结论很多时候你的回溯慢不是因为语言慢或者常数大而是因为剪枝没做对。把无效分支砍掉带来的收益通常是数量级的比任何微优化都大。7. 刷完回溯之后我的避坑清单和一点私货7.1 五个最容易踩的坑一个一个查第一个坑是忘记撤销。递归写完path.append和used[i] True都有但path.pop()或used[i] False漏了。后果前面已经演示过建议把“做选择、递归、撤销选择”当成一个整体来记忆。第二个坑是记录结果时浅拷贝翻车。Python里res.append(path)之后path后续的任何修改都会同步到res里。正确写法是path[:]或.join(path)。第三个坑是排列和组合的状态混用。排列需要used数组从整个数组里选组合需要startIndex从后面选。两者交叉使用会导致重复或漏解。第四个坑是剪枝条件剪掉了合法解。这个问题最隐蔽因为不报错。要养成分步验证的习惯先用不剪枝的版本在小数据上对拍。第五个坑是递归出口放错位置。比如数独题把return True/False写在了外层for循环之后导致递归返回值不能正确传递。遇到这种问题在纸上写出两个递归深度的调用关系比盯着代码看半小时管用。7.2 让思路变清晰的一个训练方法如果你现在对回溯还是半懂不懂我强烈建议做这样一件事找全排列[1,2,3]手动画一棵三层状态树。每个节点标注“当前路径”每层标注“可选项”。画完你会发现所谓“选择列表”其实就是你站在当前节点时能看到的孩子。used数组存在的意义就是让你在任何一个节点都能准确知道“哪些孩子还能去”。我在day25那天画了整整两页纸把全排列、组合、子集三棵树并排贴在桌子前面。之后遇到任何回溯题我第一反应就是“这题的解空间树长什么样”而不是“这题套哪个模板”。这是一个从背代码到真正理解的分水岭。7.3 给你的一点私货如果这一天的学习只能记住一句话我会记下这句回溯就是一棵树你要做的只有三件事做选择、递归、撤销。剪枝和去重都是在这棵树上做的优化状态设计决定每一层长什么样结束条件决定你在哪里摘果子。理解到这层之后再难的题也不会让你觉得回溯是个黑盒。至于刷题计划本身我给的建议是别把回溯和递归分开练。递归是回溯的骨架回溯是递归的应用。递归吃不透回溯写再多也只是死记硬背。先把几道经典的递归题搞定再回头过这一篇的每道例题你会发现自己忽然就通了。 
长河君 · 2026/10/14 23:30:07 · 阅读 1.2k 回溯算法入门：从全排列到N皇后的完整思维框架
第一次见到回溯题的时候我整整一个下午没缓过来。题目是全排列第一反应是三层循环套上去结果输入一变长的就崩了后来知道标准做法只用递归满打满算十几行代码。奇怪的是代码我可以默写出来但稍微换个题就不会了——组合还好子集也行一上N皇后直接傻眼。当时我还没意识到回溯真正的门槛根本不在代码而在“你怎么看待这棵树”。这就是标题里“算法学习day25-回溯”的含金量。第25天刚好是我刷题计划中从“会背模板”到“会设计状态”的分水岭回溯是什么、怎么剪枝、怎么去重、复杂度怎么算几乎全在这几天里被打通了。这篇文章不打算从高深的理论讲起而是把我自己踩过的坑、用顺手的写法、以及从全排列到数独的完整推导路径全部整理出来。适合刚吃透递归、正准备啃回溯的读者也适合刷过一批回溯题但总觉得差了点什么的朋友。1. 回溯到底是什么从走迷宫到解空间树1.1 一个所有人都走过的直觉模型回溯的“回溯”两个字本身就来自走迷宫。你在一个岔路口选了一条路走了一段发现是死胡同于是退回到刚才的岔路口换一条路再试。电脑干的事和这个一模一样只不过它把“岔路口”建模成了递归中的每一次调用把“试路”建模成了循环里的每一个选择。最容易被忽略的一件事是回溯不是某种新的算法套路它就是在状态空间树上做深度优先遍历只不过在遍历的过程中必须带着“撤销”这个动作。走迷宫时你没有把走过的路从地图上抹掉是因为地图是固定的但在算法题里如果你试了1这条分支回到分岔点时却不把1从路径里拿掉那下一条分支就会变成1,2、1,3而不是干净的2、3。所有写错的回溯代码十有八九都是忘了这一步。我后来特别喜欢用“试螺丝刀”来类比你面前有一把锁手里有六把看起来差不多的螺丝刀你得一把一把试试完一把就放回原位再拿另一把。放回原位就是回溯里的撤销操作。代码里对应的动作是path.pop()是used[i] False这两个操作少一个整棵树就被污染了。1.2 解空间树一眼看穿递归在干什么如果你把一次回溯算法的完整执行过程画出来会得到一棵树。树的根是空状态每个节点是一次递归调用节点下面挂着当前层可做的所有选择。拿全排列举例nums [1,2,3]时根节点路径为空第一层可以选择1、2、3生成3个分支第二层选择1之后下一层只能选2、3选择2之后下一层只能选1、3第三层填满3个位置到达叶子记录结果这棵树就是“解空间树”。理解了这棵树你就理解了回溯里几乎所有术语递归的深度等于路径长度for循环是在枚举当前层的孩子used数组和startIndex是在决定当前层能选哪些孩子剪枝是发现某个孩子下面不可能有答案时直接不往那边走去重是发现两个孩子长成一样于是只留一个。我在第25天之前一直不懂“回溯 深度优先搜索”这句话。总觉得DFS是图算法回溯是数学题。后来才想明白图里的DFS遍历的是图结构回溯遍历的是“解状态”组成的虚拟树。两者代码骨架几乎完全一样只是回溯在每个节点上多了记录和撤销的步骤。这么一对应之后学记忆化搜索、学状态压缩全都是顺水推舟的事。1.3 回溯和暴力枚举的边界在哪里有人问回溯不就是暴力吗把每个组合都枚举一遍复杂度还不是指数级这么说对也不对。暴力枚举意味着你提前知道要嵌套几层循环比如“三个数里选组合”你写三层循环“四个数”写四层。可一旦n变成变量循环层数写不出来暴力枚举直接失效。回溯用递归来代替循环层数本质上是用递归的栈深度去模拟那个不确定的嵌套层数。这个能力让回溯能处理n不固定、约束复杂、必须边走边判断的题目比如N皇后、数独、括号生成。所以更准确地说回溯是系统化的暴力枚举它把“枚举”这件事做成了可伸缩的模板。代价是时间复杂度仍然很糟糕所以才需要下一章严格训练的剪枝和去重。没有剪枝的回溯几乎是不可用的这是所有从模板入门回溯的人迟早会撞上的墙。2. 回溯模板与入门三件套全排列、组合、子集2.1 统一模板选择-递归-撤销三步曲回溯题不管怎么换皮代码骨架都是同一个。我现在的习惯是先写出这个模板再把具体题目的状态、出口、剪枝条件填进去def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 当前可做的所有选择: 做选择更新路径和状态 backtrack(路径, 新的选择列表) 撤销选择恢复路径和状态用伪代码写出来只有四行但其中“记录结果”和“撤销选择”这两步最容易翻车。记录结果时Python里如果你写res.append(path)之后path一变res里存的东西也跟着变——因为path是同一个列表对象。必须写成res.append(path[:])做浅拷贝或者存一个拼接好的字符串。至于撤销选择第五章我会专门列一个避坑清单。这个模板真正重要的地方在于你必须明确“路径”、“选择列表”、“结束条件”三样东西分别是什么。全排列的选择列表是“所有还没被用过的元素”组合的选择列表是“当前下标之后的所有元素”子集的选择列表则是“当前下标之后的所有元素且在每一层都记录当前路径”。三句话就能看出它们之间的差异在哪里。2.2 全排列用used管理“还能选谁”全排列是最适合入门的回溯题因为它的状态定义最直白路径就是一个排列路径长度等于数组长度时结束选择列表是“还没放进路径里的元素”。def permute(nums): res, path [], [] used [False] * len(nums) def dfs(): 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]) dfs() path.pop() used[i] False dfs() return res这里used数组就是“选择列表”的落地实现。它记录的是“下标是否被占用”而不是“值是否被用过”——这个区别在有重复元素的排列里会变得极其关键第四章再展开。递归结束后used[i] False被称为“回溯”的经典动作千万别漏。可以用一个临时数组验证把这个赋值注释掉结果会变成什么呢输出会非常离谱同一层的每个分支都会沿用上一分支用过的元素最终路径长度暴涨递归永不结束或结果疯狂重复。2.3 组合和子集startIndex承担了什么角色组合题combine(n, k)让你在1到n里选k个数不考虑顺序。如果不做任何限制[1,2]和[2,1]会同时出现但那在组合语义下是同一个东西。解法是用一个start参数规定下一层只能从i1开始取数这就叫“不回头”——后面的选择不能在它前面再选。def combine(n, k): res, path [], [] def dfs(start): if len(path) k: res.append(path[:]) return for i in range(start, n 1): path.append(i) dfs(i 1) path.pop() dfs(1) return res子集题则是组合的变体所有长度的组合都要。所以它不在叶子才记录而是在每个节点都记录当前路径。另一种理解是把“选或不选每个元素”展开成二叉树每次递归可以走两条路选当前元素或不选。但用start版本的写法更统一代码也更紧凑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 res2.4 三者的状态与出口差异对照把三道题放在一起对比表格比文字直观得多题型结束条件下一层起始位置记录时机核心状态子集不设出口自然遍历完成i1每个节点start组合路径长度等于ki1叶子节点start排列路径长度等于n无下标概念用used过滤叶子节点used这张表我每次做回溯题都会在心里默念一遍。题目一变先判断它是排列还是组合还是子集再决定用used还是start。把两者混用是目前刷题社区里最常见的错误有人写组合却在递归里从头循环结果同一组合出现多次有人写排列却传了个start结果能选的元素越来越少答案直接少了一大半。3. 剪枝回溯从“能跑”到“跑得动”的关键3.1 剪枝的本质提前砍掉必死的子树回溯的时间复杂度天然是指数级的。全排列n!、子集2^n当n稍微大一点不剪枝的版本会慢得让人怀疑人生。剪枝要做的事很简单在遇到某个节点时如果能判断出这个节点下面的所有分支都不可能产生合法答案就不进入这些分支。相当于走迷宫时你看到地上标着“此路不通”于是连试都不想试直接换路。但这里有个容易误解的点剪枝的前提是你有足够的判断能力。判断能力来自题目约束。比如组合总和的题combinationSum目标值target如果当前累加的和已经超过target那么继续往下加正整数只会更大可以整体放弃比如N皇后如果某列已经放了皇后那这一列的所有格子都不用再试。判断不了的分支只能老老实实走完。3.2 两类常见剪枝约束剪枝与限界剪枝第一类是约束剪枝本质是“不合法就不走”。第二类是限界剪枝本质是“即使能走到底也没有继续的价值”。我把它们分开记是因为写代码时它们的表现形式不同约束剪枝一般写在for循环里作continue条件限界剪枝一般配合排序作break。拿组合总和I来展示限界剪枝def combinationSum(candidates, target): res, path [], [] candidates.sort() def dfs(start, cur_sum): if cur_sum target: res.append(path[:]) return for i in range(start, len(candidates)): # 剪枝candidates升序后边的更大不需要再试 if candidates[i] target - cur_sum: break path.append(candidates[i]) dfs(i, cur_sum candidates[i]) path.pop() dfs(0, 0) return res这里排序是剪枝的前提。没有排序你没法确定后面元素都大于当前元素自然不能用break提前结束整层循环。这是很多教程不会单独提醒的细节限界剪枝常常和排序绑定出现把排序写在递归外面的原因就在这里。顺序写反了剪枝条件不仅不成立还会把正确答案直接剪掉程序还不报错调试起来特别难受。3.3 剪枝翻车实录我把合法解剪掉了剪枝写错方向这件事我亲身经历过一次。当时写N皇后检查列和对角线的代码是if cols[col] or diag1[row col]: continue漏掉了副对角线diag2[n - 1 row - col]。结果程序跑得飞快答案数量却比正常的n4少了两套。功能缺失完全不报错只有把答案和标准输出对比才能发现。更隐蔽的是另一种错误把对角线索引公式的边界算错导致某些列明明合法却被当成冲突跳过。这种问题没有任何报错纯粹是逻辑层面错了。从那以后我养成了两个习惯。第一个是写剪枝时一定先画一个最小样例的状态树把剪枝条件的每一步对着题目的约束逐条过一遍。第二个是默认相信自己会写错写完就用最朴素的暴力解跑一遍小数据做对拍。回溯题的剪枝是加分项但前提是功能必须正确。先保证不剪枝版本能得出正确答案再加剪枝优化这个顺序不能反过来。4. 去重陷阱为什么答案里会出现重复项4.1 重复的两个来源去重是整个回溯里最绕的部分因为它要区分两种完全不同的“重复”。第一种是顺序层面的重复。组合题里[1,2]和[2,1]是同一个答案这个用startIndex解决前面已经提到。第二种是相同值的重复。输入数组nums [1, 1, 2]时元素是有相同的。如果还按普通排列去写两个1都会被当成独立的可选项于是[1_1, 2]和[1_2, 2]会同时出现在结果里——它们位置不同、语义不同但在人眼里都是[1, 2]。题目要求去重的话就要决定这两个1在同一层只能被选一次。很多初学者会把这两种重复混为一谈一看到“去重”就在结果里加set那是下策。真正清晰的思路是先想清楚重复来自同一路径的不同顺序还是来自同一数值被当成不同元素。前者用startIndex后者用排序加used数组。4.2 三种去重方案的功能对比假设题目是“有重复元素的排列输出不重复的排列”常见有三种处理方式方案思路优点缺点结果事后去重生成全部排列排序后去重代码改动小先白跑一遍重复分支数量和开销都很大每层集合去重在for循环里用local_used记录本层已选值直白不用排序每次递归都新建集合内存和常数开销大排序used跳层数组排序后同层遇到相同值跳过剪枝彻底性能好需要理解used[i-1]状态第三种是我推荐的方案。它能避免大量无效递归在n较大时优势明显。代码长这样def permuteUnique(nums): res, path [], [] nums.sort() used [False] * len(nums) def dfs(): if len(path) len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue # 关键去重同一层相同值前一个已经回溯完used[i-1]为False if i 0 and nums[i] nums[i-1] and not used[i-1]: continue used[i] True path.append(nums[i]) dfs() path.pop() used[i] False dfs() return res4.3 排序去重的核心细节为什么是not used[i-1]上面这行去重判断是整个回溯里最容易被写反的一行。许多人背下来代码却没搞懂为什么是not used[i-1]而不是used[i-1]。关键在于nums[i] nums[i-1]意味着当前这个值和前一个值相等。现在分叉成两种情况。如果used[i-1] True说明前一个相同的值还在当前这条路径上比如路径已经选过第一个1现在要选第二个1这是合法的、正常的树枝上的连续选择。如果这时候把分支剪掉[1, 1, 2]这种答案永远出不来。如果used[i-1] False说明前一个相同的值已经被用过又被撤销了。这意味着上一棵子树已经完全走完现在回到了同一层的下一个兄弟节点。此时再选这个相同的值就会生成和上一棵子树一模一样的路径。这才是应该剪掉的情况。所以判断条件必须是“前一个相同值不在当前路径上时跳过当前值”。用not used[i-1]表达的就是这个语义。这个细节也是面试或文档里高频出现的追问点。理解它之后所有排序去重题都能无障碍套用。5. 从模板到实战N皇后、数独和更复杂的状态设计5.1 N皇后一维路径装不下二维棋盘全排列、组合、子集这三件套练熟之后我一度以为回溯没什么大不了。N皇后直接把我打回原形——因为它的路径不再是一个简单列表而是一个棋盘递归的每一层也不再对应“选择列表里的一个下标”而是对应棋盘的一行。我推荐的写法是按行递归。一行放一个皇后递归函数传入当前行号row在for col in range(n)里尝试当前行的每个列位置。只要能通过列、主对角线、副对角线三个约束检查就把皇后放下再进入row 1。这样做的好处是递归深度固定等于n每一层只负责一行状态记录也只剩三个额外数组def solveNQueens(n): res, board [], [[.] * n for _ in range(n)] cols [False] * n diag1 [False] * (2 * n - 1) # 主对角线 row col 范围 0..2n-2 diag2 [False] * (2 * n - 1) # 副对角线 n - 1 row - col def dfs(row): if row n: res.append([.join(r) for r in board]) return for col in range(n): if cols[col] or diag1[row col] or diag2[n - 1 row - col]: continue cols[col] diag1[row col] diag2[n - 1 row - col] True board[row][col] Q dfs(row 1) board[row][col] . cols[col] diag1[row col] diag2[n - 1 row - col] False dfs(0) return resN皇后教我的最重要一课是回溯的状态不一定只有一个列表它可以是多个并行状态。路径是棋盘状态是三个布尔数组两者要一起“做选择”和“撤销”。很多难一点的回溯题都是这个模式——比如数独需要维护行、列、宫三组集合本质完全一样。5.2 数独找到第一个空格直接开搜的写法数独比N皇后更接近“搜索”的原始形态因为它不是一行一行往下填而是需要不断跳转到下一个空格。一种简单稳定的写法是每层递归用双重循环找到第一个空格再尝试填入1到9的所有数字填完继续递归如果所有数字都试过还是不行就返回上一层把当前数字清掉。这里要特别注意的是数独的“剪枝”不是锦上添花而是正确性的一部分只有当前数字不冲突才允许继续往下填。用集合记录行、列、宫内已有数字冲突检查就变成三个in判断def solveSudoku(board): rows [set() for _ in range(9)] cols [set() for _ in range(9)] boxes [set() for _ in range(9)] for r in range(9): for c in range(9): if board[r][c] ! .: v board[r][c] rows[r].add(v) cols[c].add(v) boxes[r // 3 * 3 c // 3].add(v) def dfs(): for r in range(9): for c in range(9): if board[r][c] .: b r // 3 * 3 c // 3 for num in map(str, range(1, 10)): if num not in rows[r] and num not in cols[c] and num not in boxes[b]: board[r][c] num rows[r].add(num) cols[c].add(num) boxes[b].add(num) if dfs(): return True board[r][c] . rows[r].discard(num) cols[c].discard(num) boxes[b].discard(num) return False return True dfs()这种层层跳到第一个空格的做法代码量不多但对“状态撤销”的要求更高三个集合里加了什么递归返回后就要立刻删掉。用discard而不是remove是我个人的习惯虽然这里添加后必然存在但写成discard能避免撤销顺序搞错时直接抛异常调试时少一点崩溃。5.3 回溯的“亲戚”记忆化搜索与动态规划刷到第五周时我开始遇到一些“长得像回溯”却不能用回溯硬莽的题。比如某个状态在递归中会被反复计算很多次明明同一个子问题已经算过回溯还是会重算一遍。这种题的正确解往往是记忆化搜索在回溯的入口接收一个memo字典计算过某个状态就直接返回缓存结果。一个典型的场景是“从起点到终点的路径数量”。第一个版本我用回溯枚举所有路径n稍微大一点就超时。后来改成memo[(i, j)] dfs(i, j)的形式几十行代码变成几行运行时间从指数级降到线性。这件事给我的启发是回溯不只是一个个独立题型的代称它是一种搜索范式。理解了这个范式之后记忆化、动态规划这些优化手段自然都能接上——你只是不再从零开始设计“怎么枚举”而是先枚举再想办法避免重复枚举。6. 复杂度与性能优化心里有数才能不慌6.1 时间复杂度到底该怎么估回溯题面试必问复杂度但很多人的回答是笼统的一句“指数级”。更专业的说法是全排列结果数是n!每个结果拷贝路径要O(n)总时间O(n * n!)组合结果数是C(n, k)每个结果也是O(k)总时间O(k * C(n, k))子集结果数是2^n每个结果拷贝要O(n)总时间O(n * 2^n)一句话总结就是答案个数乘以生成每个答案的平均成本。剪枝可以让这个上界在实际数据上变小但理论分析通常还是按未被剪枝的情况来写。N皇后更特殊一些经典回溯的上界是O(n!)实际因为列和对角线的剪枝跑得远比这个上界快但面试里给出O(n!)并说明剪枝影响即可。6.2 空间复杂度递归深度和结果集分开看空间复杂度有两个大头。一个是递归时正在使用的那条路径占O(递归深度)另一个是最终存下的所有结果占O(答案数 * 答案长度)。如果把所有答案都存在内存里空间往往就比时间更吓人——全排列的n10时结果数组就有几百万项。有些题目只要求输出答案数量那就不要在递归里逐步append到全局列表而是用一个计数器累加空间立刻降到O(n)。6.3 实际优化时应该按什么顺序做我个人的优化顺序是先验证正确性再考虑剪枝最后才碰常量优化。具体手段从易到难大概是排序后结合限界条件提前break这是性价比最高的一步检查能否用set或布尔数组代替in list避免每次选择都遍历在状态设计上压缩比如N皇后用位运算标记列和对角线比布尔数组再快一个常数级约束条件多的题可以加启发式比如数独里优先填“可选数字最少”的空格这是MRV策略代码会复杂一些但速度提升非常明显记住一个反直觉结论很多时候你的回溯慢不是因为语言慢或者常数大而是因为剪枝没做对。把无效分支砍掉带来的收益通常是数量级的比任何微优化都大。7. 刷完回溯之后我的避坑清单和一点私货7.1 五个最容易踩的坑一个一个查第一个坑是忘记撤销。递归写完path.append和used[i] True都有但path.pop()或used[i] False漏了。后果前面已经演示过建议把“做选择、递归、撤销选择”当成一个整体来记忆。第二个坑是记录结果时浅拷贝翻车。Python里res.append(path)之后path后续的任何修改都会同步到res里。正确写法是path[:]或.join(path)。第三个坑是排列和组合的状态混用。排列需要used数组从整个数组里选组合需要startIndex从后面选。两者交叉使用会导致重复或漏解。第四个坑是剪枝条件剪掉了合法解。这个问题最隐蔽因为不报错。要养成分步验证的习惯先用不剪枝的版本在小数据上对拍。第五个坑是递归出口放错位置。比如数独题把return True/False写在了外层for循环之后导致递归返回值不能正确传递。遇到这种问题在纸上写出两个递归深度的调用关系比盯着代码看半小时管用。7.2 让思路变清晰的一个训练方法如果你现在对回溯还是半懂不懂我强烈建议做这样一件事找全排列[1,2,3]手动画一棵三层状态树。每个节点标注“当前路径”每层标注“可选项”。画完你会发现所谓“选择列表”其实就是你站在当前节点时能看到的孩子。used数组存在的意义就是让你在任何一个节点都能准确知道“哪些孩子还能去”。我在day25那天画了整整两页纸把全排列、组合、子集三棵树并排贴在桌子前面。之后遇到任何回溯题我第一反应就是“这题的解空间树长什么样”而不是“这题套哪个模板”。这是一个从背代码到真正理解的分水岭。7.3 给你的一点私货如果这一天的学习只能记住一句话我会记下这句回溯就是一棵树你要做的只有三件事做选择、递归、撤销。剪枝和去重都是在这棵树上做的优化状态设计决定每一层长什么样结束条件决定你在哪里摘果子。理解到这层之后再难的题也不会让你觉得回溯是个黑盒。至于刷题计划本身我给的建议是别把回溯和递归分开练。递归是回溯的骨架回溯是递归的应用。递归吃不透回溯写再多也只是死记硬背。先把几道经典的递归题搞定再回头过这一篇的每道例题你会发现自己忽然就通了。