回溯算法核心复盘：组合、切割、子集、排列与N皇后

刷《代码随想录》回溯篇的时候我在读完第一篇之后一度很膨胀——组合问题就那点套路backtrack函数里先判断终止条件然后for循环从startIndex开始递归进去最后pop掉。可真正回过头来刷回溯篇二的时候卡的次数远比我预想的多组合总和为什么同一个元素可以反复用组合总和II又要怎么去掉重复组合切割回文串的切割点怎么对应成下标全排列里used数组和组合里的去重为什么两码事N皇后这种棋盘题到底怎么抽象成递归参数……这些问题如果不彻底想明白背模板是没用的。这篇文章就是我把回溯篇二全部题过完之后的一次系统复盘内容包括题型分类、核心模板、去重与剪枝的区分、代码实例以及刷题过程中真实的报错记录。如果你刷到组合总和、分割回文串、子集、全排列、N皇后这道坎上这篇复盘应该能帮你少走不少弯路。1. 回溯篇二到底在“二”些什么1.1 从组合题到搜索树的重构回溯篇一基本围绕组合问题展开77组合、216组合总和III、17电话号码字母组合。这三道题有一个共同特征候选元素本身不重复每层递归从startIndex开始横向扫描递归深度由path长度控制。说白了这就是在“选还是不选”的搜索树里走一条固定深度的路径只要记熟模板大多数人都能比较顺畅地写出来。回溯篇二则把问题层面拉高了一个维度。从题目类型上看它覆盖了组合总和39、组合总和II40、分割回文串131、复原IP地址93、子集78、子集II90、全排列46、全排列II47、N皇后51、解数独37这一串题目。这些题目表面上天差地别但站在搜索树的角度看它们其实是回溯的四种不同变体组合类变体核心是“如何限定起点避免组合重复”。切割类变体核心是“切割线位置如何映射成下标”本质还是组合。子集类变体组合问题收集的是叶子节点子集问题收集的是所有节点。排列类变体不再有startIndex的概念要用used数组标记“位置是否被占用”。棋盘类变体把棋盘行数当作递归深度把列数当作横向选择本质上仍是多叉树搜索。很多人刷到回溯篇二觉得吃力是因为还停留在“套模板”的层面没有把问题拆解成“横向遍历什么、纵向递归什么、什么时候撤销”。当你把这几个问题想清楚N皇后和解数独其实也只是换了个场景的模板题。1.2 为什么“回溯”叫“带撤销的深度优先搜索”我最早听到“backtrace栈回溯”这个词的时候第一反应是这不就是DFS深度优先搜索换了个名字后来刷得多了才体会到回溯和普通DFS最大的区别就是那行“撤销操作”。举一个很直观的例子。假设你在走一个迷宫DFS会一条道走到黑不通就往回退一步换条路再走。普通DFS的“回退”体现在函数调用栈当前递归返回后调用栈会自动弹栈局部变量随之销毁。但回溯里我们通常把path、used这类状态放在递归函数外部或者作为引用传参它们不会因为函数返回而自动恢复。所以我们必须手动把刚刚做的选择撤掉否则下一个分支会带着错误的历史数据继续搜索。这个过程在栈上的表现非常清楚每调用一次递归就在调用栈上压入一个栈帧每次return就弹出一个栈帧。递归深度就是栈的最大深度。而手动撤销操作相当于在业务数据层面也维护了一个“状态栈”path的append和pop恰好就是压栈和弹栈。这也是为什么这类问题用递归写最自然因为函数调用栈帮我们保存了每一层的现场。从代码随想录的角度看回溯本质上是在遍历一棵虚拟的多叉树。树的深度由递归决定树的宽度由for循环决定。回溯篇一里树的层数基本等于组合元素个数到了回溯篇二树的形态开始变得复杂有的树可以重复使用元素有的树要在节点上做合法性校验有的树要收集所有中间节点。弄懂这棵搜索树长什么样比会背模板重要得多。2. 模板与思维升级看懂搜索树才能写对代码2.1 回溯七行模板与参数设计网上关于回溯模板的总结很多代码随想录里的版本也非常经典。我这里以自己的习惯给出一版Python模板def backtrack(path, choices): if 满足终止条件: res.append(path[:]) return for 选择 in choices: 做选择 backtrack(path, 新的选择列表) 撤销选择实际刷题时我会把模板展开成更明确的样子def dfs(startIndex, currentSum): if currentSum target: res.append(path[:]) return for i in range(startIndex, len(candidates)): if currentSum candidates[i] target: break path.append(candidates[i]) dfs(i, currentSum candidates[i]) path.pop()这段代码是从39组合总和里摘出来的已经天然包含了排序剪枝。可以看到真正核心的只有四件事终止条件怎么写决定什么时候把path存入结果。for循环从哪开始组合类问题用startIndex排列类问题从0开始。递归参数传什么传i还是i1传不传sum、row等状态变量。撤销操作放哪必须在递归返回之后、下一次for循环迭代之前。参数设计是整个回溯题的灵魂。startIndex的作用是告诉每一次递归“横向扫描的起点在哪里”它决定了搜索树的分支范围used数组的作用是标记“哪些位置已经被占用”它决定了排列问题中每个元素是否能被重复选择额外的状态变量如currentSum、row则负责剪枝和合法性判断。把这些参数想清楚代码自然就出来了。2.2 剪枝的两个基本动作排序与提前终止回溯如果不剪枝很多题目会直接超时。代码随想录里反复强调“剪枝”的重要性我刷下来的感觉是回溯的剪枝手段虽然很多但90%的场景只用得到两个动作——排序和提前终止。先说排序。为什么要排序因为很多剪枝依赖“数字大小有序”这个前提。比如组合总和39里candidates先排序后在for循环里一旦发现currentSum candidates[i] target就可以直接break因为后面的元素只会更大继续遍历没有意义。如果不排序这个条件就不成立只能continue或者硬着头皮搜到底。再说提前终止。它通常和排序配合使用。在组合总和II40里我们不仅要剪掉超target的分支还要剪掉同层重复值的分支。做法是if i startIndex and candidates[i] candidates[i - 1]: continue这一行的作用是“同一树层不使用同一数值”。因为数组排序后相同的数字会挨在一起在横向for循环里第一次遇到某个值时已经把包含这个值后续所有可能的组合都搜完了再遇到相同的值搜出来的组合必然重复。所以直接跳过它。关于复杂度回溯类题目的理论复杂度通常是指数级。以组合/子集问题为例搜索树的节点数上界是O(2^n)每个节点都可能需要O(n)的时间做path拷贝所以总时间复杂度是O(n·2^n)。空间复杂度主要来自递归深度和path存储是O(n)。剪枝虽然不能改变最坏复杂度但在实际数据上往往能把搜索空间砍掉一个量级。2.3 撤销操作为什么要放在递归返回后我见过不少初学者在写回溯时把撤销操作放错位置导致程序跑出来的结果千奇百怪。最常见的错误是把path.pop()写在了递归调用之前或者写在了递归函数内部的其他地方。先看一个错误示范for i in range(start, len(nums)): path.append(nums[i]) path.pop() # 错误递归之前就撤销了 dfs(i 1)这样写会让path在进入下一层递归之前就已经被清空每一层的状态都是乱的最终结果要么全是空列表要么直接死循环。正确的顺序一定是先做选择再递归递归返回后立刻撤销。这个顺序对应到搜索树上的语义就是沿着一条分支往下走时path要不断累加走到底之后往回退一步把最后加进去的元素弹出来才能继续尝试同一层的下一个分支。Python里还有一个特别隐蔽的坑res.append(path[:])写成res.append(path)。因为path是列表属于可变对象append进res的是引用而不是值。搜索过程中path会不断变化最后res里所有元素都会变成同一个path的最终状态。我最早刷78子集时就在这里翻过车出来的全是空列表。C里vector是按值赋值的所以res.push_back(path)没问题Java里则要new ArrayList(path)。语言差异一定要心里有数。3. 四大题型逐个拆解从切割到棋盘3.1 组合总和无限取与去重的边界39组合总和是回溯篇二的第一道题也是最容易被“可无限取”这个条件绕晕的题。题目给了一个无重复元素的candidates数组和一个target要求返回所有和为target的组合每个元素可以被无限次使用。“无限次使用”在代码上只体现在一个地方进入递归时传的是i而不是i1。class Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: candidates.sort() res, path [], [] def dfs(start, total): if total target: res.append(path[:]) return for i in range(start, len(candidates)): if total candidates[i] target: break path.append(candidates[i]) dfs(i, total candidates[i]) path.pop() dfs(0, 0) return res这里最需要想明白的是为什么允许重复取还要用startIndex因为组合问题里[2,2,3]和[3,2,2]被视为同一个组合。如果每次递归都从数组开头扫描必然会出现顺序不同的重复组合。startIndex保证了横向扫描只能往后走不会回头选已经考虑过的元素。至于某个元素可以取多次则是通过递归里传i实现的——取完2之后下一层仍然可以从2开始。这题的剪枝也很好理解。排完序后一旦total candidates[i] target后面的元素更大只会更超直接break。我实测过不排序不剪枝在某些极端用例下会慢到怀疑人生排序加break之后基本都能秒出。3.2 切割类问题下标即切割线131分割回文串要求把一个字符串s划分成若干个子串每个子串都是回文串返回所有划分方案。很多人第一次看到这题会觉得它和组合没关系其实它就是把“选数字”换成了“切割字符串”。核心思路是把startIndex理解为“当前切割线的起始位置”for循环里的i则是“切割线的终点位置”。每次从s[start:i1]切出一个子串判断它是不是回文如果是就切下去然后从i1开始继续递归处理剩余部分。class Solution: def partition(self, s: str) - List[List[str]]: res, path [], [] def dfs(start): if start len(s): res.append(path[:]) return for i in range(start, len(s)): sub s[start:i 1] if sub sub[::-1]: path.append(sub) dfs(i 1) path.pop() dfs(0) return res这个模板和组合题几乎一模一样区别只是终止条件从“sum target”变成了“start len(s)”以及多了一个回文判断。切割点选择完整个字符串后递归结束。93复原IP地址是同一类问题的加强版。它要求把字符串切成四段每段都是合法的IP段长度1到3数值0到255不能有前导0。切割逻辑不变只是多了两个校验条件。特别注意前导0的判断如果s[start] 0那么这一段只能长度为1不能继续往后扩。我在第一次写的时候忽略了这一点导致输出里出现了01.2.3.4这种非法IP。3.3 子集类问题收集的是搜索树的每个节点78子集要求返回数组所有子集。组合问题收集的是叶子节点path长度达标的节点子集问题则不同——搜索树的每一个节点都是一个合法子集。所以收集结果的时机不是终止条件里而是在每次进入dfs时class Solution: def subsets(self, nums: List[int]) - List[List[int]]: 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注意这里连显式的终止条件都不需要。当start等于len(nums)时for循环自然结束递归返回。空集怎么出来的第一次调用dfs(0)时path还是空的直接append进去就得到了空集。单元素子集则是每个for循环里只走一层递归时收集到的。90子集II是在78的基础上加了一个“去重”条件原数组可能包含重复元素但结果中不能出现重复子集。做法和40组合总和II一模一样先排序然后在for循环里加上i start且nums[i] nums[i-1]时continue。这就是“同层去重”。3.4 排列类问题used数组的另一个身份46全排列和组合问题的差异非常本质。组合里[1,2]和[2,1]是同一个集合所以靠startIndex避免回头选元素排列里[1,2]和[2,1]是两个不同结果每个元素都可能出现在任何位置因此每次for循环都要从数组头开始扫描。那怎么知道某个元素是否已经用过答案是used数组class Solution: def permute(self, nums: List[int]) - List[List[int]]: 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 resused数组标记的是数组下标而不是元素值。因为元素值可能有重复但数组下标是唯一的。在递归回溯时不仅要pop path还要把used[i]恢复为False否则后续分支没法再使用这个元素。47全排列II则把难度再提一档数组本身有重复元素要求结果不能有重复排列。很多人直接照抄40题的“排序 i startIndex去重”结果发现根本不适用。排列问题没有startIndex正确做法是排序后加上if i 0 and nums[i] nums[i - 1] and not used[i - 1]: continue这个判断的含义是在同一层循环中如果前一个相同元素没有被使用说明当前这个元素是重复值跳过。另一种写法是把not used[i-1]改成used[i-1]也能通过但语义不同前者是树层去重后者是树枝去重。代码随想录里对这两种写法有详细的对比我个人的建议是用not used[i-1]因为它的语义更直观——只有前一个相同元素真的没被占用时才说明当前是在同一层遇到了重复值。3.5 棋盘类问题把回溯当成系统性的枚举51 N皇后可能是回溯篇里最劝退的一道题但一旦你看穿它的结构其实并不复杂。我们把棋盘的行号作为递归深度把列号作为for循环的横向选择。每一层递归处理一行尝试把皇后放到这一行的某一列放之前检查是否和之前行已放的皇后冲突。class Solution: def solveNQueens(self, n: int) - List[List[str]]: res [] board [[.] * n for _ in range(n)] def isValid(row, col): for i in range(row): if board[i][col] Q: return False if col - (row - i) 0 and board[i][col - (row - i)] Q: return False if col (row - i) n and board[i][col (row - i)] Q: return False return True def dfs(row): if row n: res.append([.join(r) for r in board]) return for col in range(n): if isValid(row, col): board[row][col] Q dfs(row 1) board[row][col] . dfs(0) return resisValid里的三个判断分别对应同列冲突、主对角线冲突、副对角线冲突。主对角线上的元素满足行差等于列差副对角线上的元素满足行差等于负列差用这些关系就能在O(n)时间内完成检查。37解数独比N皇后更进阶一点因为它在每一层递归里都要双重循环找一个空位。思路是把“尝试填入数字”当作选择每次找到第一个.尝试填入1到9如果合法就继续递归填满了就返回True9个数字都不行就返回False并回溯。由于只需要一个解递归函数的返回值是布尔值这在回溯里也是一个常用模式某些问题只需要一个可行解时递归返回bool能提前终止整个搜索。4. 组合、子集、排列三者的去重对比4.1 同层去重 vs 深度去重去重是回溯篇二里最容易出错的点。我总结下来去重可以分成两个维度同层去重和深度去重。同层去重说的是在搜索树的同一个节点下for循环迭代到重复值时跳过后续的重复分支。因为第一个重复值已经覆盖了所有后续分支的搜索再走一遍必然产生重复结果。典型写法就是40和90里的排序加i startIndex判断。深度去重说的是在递归的纵向过程中同一个元素不能重复使用。组合问题靠startIndex天然实现了这一点因为起点只往后移排列问题则必须靠used数组显式标记。用一个表格来对照会更清楚问题类型去重目标手段典型题目组合无重复元素避免元素重复取startIndex 递归传i177、216组合可重复取保证组合不重但元素可取多次startIndex 递归传i39组合含重复元素结果不能有重复组合排序 i startIndex去重40子集含重复元素结果不能有重复子集排序 i startIndex去重90排列无重复元素每个元素只能用一次used数组46排列含重复元素每个元素只能用一次 结果不重复排序 used数组 同层去重474.2 什么时候必须排序、什么时候不能排序排序是去重和剪枝的好帮手但并不是所有题都能排序。我踩过的坑就是遇到去重一律先排序结果在491递增子序列上翻车了。491要求找出所有递增子序列原数组顺序不能改变因为“递增”是相对于原序列顺序而言的。排序会破坏原顺序所以这题不能用排序去重得用另一种做法在同层循环里用一个set记录本层已经使用过的值遇到重复值就跳过。这是回溯里第二种去重手段。反过来91复原IP地址也不能排序因为IP地址的段顺序来源于s的字符顺序排序等于直接改题。N皇后和数独更不需要排序。所以“什么时候排序”的判断标准很简单如果题目要求结果和数组原始顺序相关不能排序如果只是求子集/组合/排列且结果顺序无关优先排序。4.3 Python切片、深拷贝与其他语言差异跨语言刷题时最容易忽略的是值拷贝问题。Python里list是引用类型path直接append到res中会导致所有结果指向同一个对象所以必须用path[:]做切片拷贝。C的vector是值类型res.push_back(path)会拷贝一份所以C代码里很少见到显式拷贝操作。Java则必须写new ArrayList(path)。另一个和语言相关的坑是Python切片的越界行为。s[start:i1]即使i1超出字符串长度Python也不会报错而是返回从start到结尾的子串这在切割问题里反而让代码更安全。C的substr规则稍有不同如果下标超过长度会抛出out_of_range异常写的时候要提前处理。5. 常见问题与排查心得5.1 常见报错与逻辑错误速查表刷完整个回溯篇二我整理了一张速查表基本覆盖了最常见的报错场景现象可能原因解决方案结果集里全是空列表res.append(path)写成了引用拷贝改成res.append(path[:])组合结果大量重复数组未排序就做相邻去重先排序再判断nums[i]nums[i-1]元素被重复使用递归参数传错可重复取传i不可重复取传i1全排列结果重复未用used数组或used去重位置不对排序 not used[i-1]判断切割问题无限递归startIndex没有推进检查递归调用是dfs(i1)还是dfs(i)IP段出现前导0未对0开头的段做单独处理段长大于1且以0开头时直接跳过N皇后isValid越界对角线检查缺少列坐标范围判断加if col-row-i0等条件解数独没有输出递归没有返回值或未正确return空位填完return True无解return False这张表里的问题我几乎全踩过一遍。尤其第一条几乎每个人写Python回溯都会踩一次。5.2 刷题节奏与复盘方法代码随想录的回溯篇一共十四道题左右回溯篇二大概占十道。我的建议是不要贪快按组合、切割、子集、排列、棋盘的顺序分五天刷每天两到三道每道题至少写两遍。第一遍照着模板写目标是跑通第二遍放下模板在白纸上画出搜索树再凭理解写出代码。我在刷40题的时候就是先画树形图把重复分支标出来才真正理解了“同层去重”的含义。画树形图这个方法看起来笨但对付回溯题效果奇好。另外可以把相似题放在一起对比。比如把39和40放在一起刷就能看出“可重复取”和“数组含重复元素”是两个完全不同的条件把78和90放在一起就能理解子集去重和组合去重其实是一回事把46和47放在一起就能明白used数组加排序去重的组合拳。这种对比式刷法比一题一题孤立地刷效率高得多。5.3 我踩过的坑说几个我实际踩过的坑都是报错信息不明显、但会让人卡很久的。第一个坑40题里我忘了排序直接在for循环里写if candidates[i] candidates[i-1]: continue。因为原数组里相同值不相邻所以这个判断形同虚设结果大量重复组合。排查了很久才发现问题不是出在递归逻辑而是出在预处理。遇到去重先排序这个动作必须刻在脑子里。第二个坑47题里我把used[i-1]的写法搞反了写成了if i 0 and nums[i] nums[i-1] and used[i-1]: continue。跑出来结果倒是正确但效率明显变慢。后来看了代码随想录的解释才明白used[i-1]为True时跳过属于树枝去重它在某些场景下会额外剪掉一些本来可以继续搜的分支虽然结果对但语义不对可读性也差。最终我还是改成了not used[i-1]的写法。第三个坑37解数独里valid函数检查3x3宫格时我一开始写的是for i in range(row//33, row//333)忘了优先级的括号导致行列坐标计算混乱。后来把r // 3 * 3单独算成r0 (row // 3) * 3才彻底解决。这种小问题在回溯题里特别容易发生因为它不是语法错误而是逻辑错误靠调试器很难一眼看出来。6. 参考题单与最后的一点心得6.1 回溯篇二刷题清单如果你正准备系统性刷这部分我把自己过完的题单列出来按顺序刷就好题号题目核心考点备注39组合总和可重复取 排序剪枝理解传i和传i1的区别40组合总和II同层去重 排序预处理树层去重的样板题131分割回文串切割线映射下标 回文判断组合思想迁移到字符串93复原IP地址切割 合法性校验注意前导0和段长度限制78子集收集搜索树所有节点理解节点收集时机90子集II子集去重与40共用同一套去重模板491递增子序列不能排序情况的去重同层用set去重46全排列used数组标记排列和组合的根本差异47全排列II排序 used去重理解not used[i-1]语义332重新安排行程回溯 字典序贪心可作进阶题要求遍历所有边51N皇后棋盘回溯 对角线校验行递归 列枚举37解数独二维递归 bool返回值二维棋盘搜索的收官题这十二道题覆盖了回溯的几乎所有典型场景。332题相对特殊它更接近图论里的欧拉路径问题我把他放在最后刷作为查漏补缺。6.2 写在最后的经验最后分享一个我自己刷下来的体会代码随想录回溯篇二里的所有题目第一步都不是写代码而是画树形图。不管是组合、切割、子集还是排列你只要把那棵搜索树的每一层画出来横向是什么选择、纵向递归到哪个状态、什么时候撤销代码基本就水到渠成了。包括N皇后也一样——树的每一层是棋盘行for循环里枚举的是列递归下去就是下一行。画出树形图之后你会发现回溯题之间的差异远没有想象中那么大。还有一个小技巧是如果某道回溯题总是超时先检查有没有排序、有没有在for循环里加提前break如果没有超时但结果不对把“撤销”那一行注释掉看一眼输出你会立刻明白撤销操作到底在干什么。这种“破坏性调试”虽然看起来很笨但比对着代码干想有效率得多。