1. 从递归模板到剪枝艺术回溯算法的进阶地图说实话写这个系列的第三篇之前我特意回去翻了翻前两篇的评论区。很多朋友留言说看完组合问题和排列问题的解法后回溯算法的基本框架算是吃透了但一遇到“分割回文串”“复原IP地址”这类题目还是容易卡壳。还有人问是不是所有回溯题都长一个样什么时候该剪枝剪枝到底怎么剪才能不漏解这篇就专门聊这些进阶场景。我默认你已经掌握了回溯算法的核心模板——就是那个“路径记录、选择列表、终止条件”的经典结构。如果还没完全掌握建议先回头把组合、排列、子集这几类基础题做熟练再来啃今天的内容。今天的重点有三个切割类问题的建模思路、去重与剪枝的进阶技巧、以及对棋盘类问题的深度剖析。这三块内容放在 part03 里是因为它们不再是简单的模板套用而是需要对问题做一层“翻译”——把看似不相关的问题转化成语义明确的选择树再用回溯法去遍历。这才是回溯算法真正值钱的地方。提示这篇文章里的代码全部用 Python 编写平台是 LeetCode 风格但思路通用于所有支持递归的语言比如 Java、C、Go 都一个套路。2. 切割类问题把“切哪里”变成“选哪个”2.1 为什么切割问题和回溯天然契合先聊一个我在带新人时常问的问题给你一个字符串让你切出所有可能的回文子串组合你会怎么做大部分人第一反应是先找出所有回文子串再去拼。这个思路不能说错但实现起来非常绕。因为你一旦先找子串后面组合的时候需要手工维护状态很容易漏解或重复。正确思路是把“切割”这件事转换成“在字符之间的缝隙处做选择”。一个长度为 n 的字符串有 n-1 个可以下刀的位置。每个位置选还是不选就是一个标准的二叉选择树。这就是回溯算法的用武之地。拿aab来举例你可以画一棵这样的选择树第一刀切在位置1左边是a右边递归处理ab第一刀切在位置2左边是aa右边递归处理b第一刀切在位置3左边是aab判断不是回文剪掉这个过程的本质是把“所有切割方案”投影成一棵递归树树上每条从根到叶子的路径就是一组完整切割方案。回溯就是做深度优先遍历遍历完所有合法路径。2.2 分割回文串的完整代码与逐行解读直接上代码这个解法我实测过性能和可读性都比较平衡def partition(self, s: str): res [] path [] n len(s) def dfs(start): if start n: res.append(path[:]) return for end in range(start, n): substr s[start:end 1] if substr substr[::-1]: path.append(substr) dfs(end 1) path.pop() dfs(0) return res这段代码里start表示当前切割的起始位置end表示结束位置。每次从start出发枚举所有可能的结束位置然后判断这个子串是不是回文。如果是就加入路径递归处理剩余部分递归返回后弹出尝试下一个结束位置。这里有个细节值得多说一句为什么终止条件是start n而不是别的因为当起始位置走到字符串末尾时说明前面所有的切割方案已经形成了一个完整的划分而且每个子串都在入队前验证过是回文。这个条件写起来简单但背后是有严谨逻辑的。另一个细节是path[:]这个拷贝操作。回溯过程中path是复用的如果不拷贝直接res.append(path)最终得到的结果会全是空列表因为你最后一步会把它弹空。这个坑我见过不下十次。2.3 切割问题的剪枝时机先判断还是先递归切割问题的剪枝其实比较简单因为判断条件就一个子串是否为回文。但有一个顺序问题值得琢磨——是先判断再入队还是入队后在递归里判断我的建议是先判断再入队。原因有二第一能省掉很多无效的递归调用。如果子串不是回文那么以这个子串为根的所有子树都不需要遍历提前砍掉能节省大量时间。第二代码更直观。入队的一定是合法元素终止条件里只需要检查start n逻辑更清爽。不过有些题目判断条件比较复杂比如后面要讲的复原IP地址需要同时校验数值范围和前导零这种情况下我倾向于写一个独立的校验函数而不是在 dfs 里堆一堆 if 条件。这样主逻辑清晰校验逻辑也能单独测试。3. 去重进阶从“排序跳过”到“选代表”3.1 组合总和 II 里的同层去重逻辑组合总和 II 这道题核心难点在于候选数组里有重复数字但结果集合里不允许有重复组合。举个例子candidates [1, 1, 2, 5]target 8。如果你不去重会得到两组[1, 2, 5]因为两个 1 都可以和[2, 5]组合。但题目说结果里只能留一个。作为对比组合总和 I 的数组里没有重复数字所以不需要去重直接枚举组合就行。多了重复数字之后选择的语义就变了每个位置的数字不再是一个独立的决策而是“相同数值的数字属于同一个决策层级”。代码层面最标准的写法是这样的def combinationSum2(self, candidates, target): candidates.sort() res [] path [] n len(candidates) def dfs(start, remain): if remain 0: res.append(path[:]) return for i in range(start, n): if i start and candidates[i] candidates[i - 1]: continue if candidates[i] remain: break path.append(candidates[i]) dfs(i 1, remain - candidates[i]) path.pop() dfs(0, target) return res关键是if i start and candidates[i] candidates[i - 1]: continue这一行。它做的事情是同一层递归中如果当前数字和前一个数字相同就跳过。注意i start这个条件是必须的它保证了“在递归的下一层可以使用重复数字”。比如[1, 1, 2]在第一层选了第一个 1 之后下一层可以从第二个 1 开始这是合法的但第一层已经处理过第一个 1 了如果第一个 1 不行第二个 1 一定也不行因为剩余目标和是相同的。3.2 全排列 II 里的同层去重全排列 II 的去重逻辑大体类似但细节上有差异因为排列问题每个位置的选择是互斥的——数字一旦被用过就不能再用第二次。这时候去重要结合used数组def permuteUnique(self, nums): nums.sort() 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 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 res这里not used[i - 1]这个条件值得展开讲。它是用来判断当遇到相同数字时前一个相同数字在当前递归路径上是否已经被使用过。如果used[i - 1]为 True说明前一个数字在当前路径上被使用了这是合法的——因为两个相同数字可以同时出现在排列里只是顺序不同。如果used[i - 1]为 False说明前一个数字已经被撤销了那当前分支和之前处理过的分支是完全等价的跳过。这个技巧的本质是“选代表”每一层递归中相同数字只允许在第一个位置被选中一次其他位置的情况已经被第一个代表覆盖。3.3 去重总结一个通用判断框架踩过很多坑之后我总结了一个相对通用的判断框架你用的时候只需要回答三个问题问题里重复元素的约束是什么组合里每个元素只能用一次还是可以重复使用结果集去重还是路径内去重前者用排序同层跳过后者用 visited 标记去重靠排序可行吗如果原顺序有意义就不能随便排序得改用其他方法我把这个框架整理成一个参考表方便你对照使用场景去重手段关键条件适用题目组合问题 元素可重复使用允许同值元素同层下次递归不用去重直接i启动组合总和 I组合问题 元素不可重复使用排序 同层跳过i start and nums[i] nums[i-1]组合总和 II排列问题 全排列去重排序 visited配合同层跳过not used[i-1] 时跳过全排列 II子集问题 去重排序 同层跳过i start and nums[i] nums[i-1]子集 II4. 复原IP地址一个被忽视的边界条件重灾区4.1 把IP地址切割套进回溯框架复原IP地址这道题本质上还是切割问题只是比回文串切多了一层校验标准每段必须是 0 到 255 之间的整数且不能有前导零除非数字本身是0。题目的要求是给定一串数字字符串比如25525511135还原所有可能的合法IP地址。输出是255.255.11.135和255.255.111.35这样的结果。转换为回溯问题的思路很简单从起点开始枚举第一个IP段的结束位置可以是1位、2位、3位校验合法性后递归处理剩余部分。终止条件是已经找到了4段且刚好把字符串用完。def restoreIpAddresses(self, s): res [] path [] def is_valid(segment): if len(segment) 1 and segment[0] 0: return False return 0 int(segment) 255 def dfs(start, seg_count): if seg_count 4: if start len(s): res.append(..join(path)) return if start len(s): return for end in range(start, min(start 3, len(s))): segment s[start:end 1] if is_valid(segment): path.append(segment) dfs(end 1, seg_count 1) path.pop() dfs(0, 0) return res我自己写这段的时候一开始犯过一个错只校验了int(segment) 255忘了校验前导零。结果在010010这种测试用例上直接翻车——它产出了0.10.0.10和0.100.1.0等结果但漏掉了更多合法答案因为01被错误地当成合法段放行了。4.2 边界条件的枚举与防御IP地址的边界条件如果不整理很容易疏漏。我把它列成一个清单写代码前对着过一遍字符串长度小于4或大于12直接返回空集——因为IP地址至少4位、最多12位每段3位。每段长度必须为1到3位。超出这个范围的枚举可以直接跳过。每段不能有前导零。唯一允许以0开头的情况是段本身就是0。每段的整数值必须小于等于255这个判断要在转整数之后做。4段必须恰好覆盖整个字符串不能多也不能少。这些条件单独看都不复杂但合在一起就容易漏。我推荐的写法是把校验逻辑独立成函数不要和 dfs 主逻辑混在一起方便单测。5. 棋盘类问题N皇后与解数独的通用解法5.1 N皇后把行列冲突映射为坐标公式切割问题是沿着字符串“切一刀”N皇后则是在棋盘上“放棋子”。表面上看风马牛不相及但回溯的内核完全一致每一层递归选择一个位置放入皇后判断是否合法不合法就剪掉合法就继续深入。N皇后的核心难点不在回溯而在于冲突检测的效率。如果每次放皇后都去扫描整个棋盘复杂度会飙到 O(n!·n²)虽然 n 小的时候还能跑但纯属浪费。我的做法是用三个集合来记录冲突状态cols记录哪些列已经有皇后diag1记录哪些“主对角线”已经有皇后用 row - col 标识diag2记录哪些“副对角线”已经有皇后用 row col 标识为什么要用 rowcol 和 row-col这是棋盘坐标的一个性质同一条主对角线上所有格子的 row - col 相同同一条副对角线上所有格子的 row col 相同。你把一个 4x4 棋盘的每个格子标上 rowcol就会看到副对角线上的数字都一样。有了这三个集合检查一个位置是否合法就变成了三次 O(1) 的查表操作def solveNQueens(self, n): res [] cols, diag1, diag2 set(), set(), set() queens [] def dfs(row): if row n: board [. * q Q . * (n - q - 1) for q in queens] res.append(board) return for col in range(n): if col in cols or (row - col) in diag1 or (row col) in diag2: continue queens.append(col) cols.add(col) diag1.add(row - col) diag2.add(row col) dfs(row 1) cols.remove(col) diag1.remove(row - col) diag2.remove(row col) queens.pop() dfs(0) return res这里每行只放一个皇后所以不需要检查行冲突。这种写法在 n8 时性能表现相当不错实测在普通笔记本上能稳定跑进 0.2 秒比很多人用二维数组扫描的版本快一到两个数量级。注意diag1.add(row - col)和diag1.remove(row - col)中的括号不要去掉。我在重构这段代码时曾经因为运算符优先级问题误把row - col in diag1当成了row - (col in diag1)查错花了半小时。5.2 解数独二维回溯与剪枝策略解数独是另一个经典的棋盘回溯题但它比N皇后更复杂一点因为决策点不是固定的——你需要先找到一个空格再尝试填入数字。基础的解法逻辑很直白def solveSudoku(self, board): def find_empty(): for i in range(9): for j in range(9): if board[i][j] .: return i, j return None def is_valid(row, col, ch): for i in range(9): if board[i][col] ch: return False if board[row][i] ch: return False box_row, box_col 3 * (row // 3) i // 3, 3 * (col // 3) i % 3 if board[box_row][box_col] ch: return False return True def dfs(): empty find_empty() if not empty: return True row, col empty for ch in 123456789: if is_valid(row, col, ch): board[row][col] ch if dfs(): return True board[row][col] . return False dfs()这个版本能找到解但性能一般。原因在于find_empty每次都从头扫描且is_valid完整扫描了三次 9 长度。如果需要优化有两个方向方向一维护三个布尔矩阵rows[9][9]、cols[9][9]、boxes[9][9]分别记录每行、每列、每个九宫格中数字是否已被使用。填一个数字时同时更新三个矩阵撤销时恢复。这样is_valid变成 O(1)。方向二优先选择候选数字最少的空格来填充MRV 启发式。这个策略能大幅减少搜索空间尤其是对于空格外多的高级谜题效果立竿见影。5.3 棋盘问题的复杂度直觉聊到算法题就绕不开复杂度。N皇后的时间复杂度是 O(n!)因为第一行有 n 个选择第二行最多 n-1 个以此类推。加上剪枝后实际搜索空间远小于 n!但最坏情况还是这个量级的。解数独的时间复杂度理论上是 O(9^m)m 是空格数。但经过 MRV 启发式和约束传播后实际搜索空间会急剧缩小。遇到难解的空白棋盘普通回溯可能要跑几秒甚至更久但优化后通常毫秒级就能出解。有一点我想特别说明算法竞赛里经常讨论“复杂度”但做工程和刷题不必过度纠结数学推导。你更需要建立的是直觉——这个剪枝能砍掉多少无效分支那个优化值不值得做。回溯算法的剪枝本质都是在“用判断换遍历”砍掉一个分支省下的时间如果小于做判断本身的开销那这个剪枝就是负优化。6. 常见问题排查与排错实录6.1 结果全是空列表path引用问题这个坑在前面提过一次但值得单独列为一条。当你执行res.append(path)而不是res.append(path[:])时存入结果的是path的引用而不是快照。递归返回时path.pop()会同步修改res里已存的内容最终res里的所有元素都指向同一个已经被弹空的列表。排查方法很简单在dfs返回后打印res如果里面全是[]基本就是这个原因。修复方法就是改为path[:]浅拷贝或者list(path)。6.2 去重不彻底排序顺序和剪枝条件的错位另一个高频问题是去重条件写错。很多人写组合总和 II 的去重时把条件写成if i 0 and candidates[i] candidates[i-1]忘了加i start。区别在哪正确的i start只在同一层递归中去重允许在不同深度使用相同值。错误的i 0在每层递归里都会和自己前面位置的值比较会导致漏解。比如[1, 1, 2, 5]走到第二层时i1因为candidates[1] candidates[0]直接把第二个1跳过了但这一层的起点是 1选[1,1]这个组合本来是完全合法的。解决这个问题的记忆口诀是“同层去重用 start全局去重用 used”。组合类问题用 start排列类问题用 used。6.3 递归死循环终止条件缺失或错误还有一类比较隐蔽的 bug是终止条件写错导致死循环。典型场景是切割问题中递归调用时传入的是start 1而不是end 1。比如在分割回文串的代码中# 错误写法 dfs(start 1) # 正确写法 dfs(end 1)如果写成了start 1当 end 大于 start 时下一层递归的起始位置会往回跳导致同一层内出现重复枚举甚至无限递归。排查方法是在 dfs 的入口加一个打印语句输出 start 和 path 的当前值观察 start 是否严格递增。如果出现递减或不变立刻就能定位到参数传递的 bug。6.4 回溯算法问题速查表我把这些坑整理成一个查错表调试的时候对照着看症状可能原因修复方法结果全是空列表res.append(path) 未拷贝改成 path[:] 或 list(path)解数量偏多忘记去重或去重条件过宽检查排序、同层跳过条件解数量偏少去重条件过严如 i 0 误写改回 i start无限递归递归参数未正确收敛检查 start/end 的传参输出顺序不对排序影响原顺序若顺序敏感则去掉排序改用used区间未重置全局数组可能残留上次结果每次新建或显式清理7. 回溯算法的三种剪枝手段与决策框架7.1 可行性剪枝、优化剪枝、重复性剪枝回溯算法的剪枝手段我习惯把它分成三类这样理解和记忆都更系统可行性剪枝判断当前路径是否还有可能到达合法解。比如组合总和II中如果candidates[i] remain那么后续更大的数字也一定超过直接 break。这个剪枝通常在枚举循环内完成。重复性剪枝剪掉等价分支同一层递归中相同数值的元素只处理一次。典型手段就是排序 同层跳过。对称性剪枝利用问题的对称性质减少搜索空间。N皇后中你可以只搜索前半列的解再通过镜像生成剩余部分解数独中优先选择候选数字最少的空格也是一种变向剪枝。这三种剪枝不是互斥的实战中经常叠加使用。以组合总和II为例先排序用 break 做可行性剪枝用跳过重复值做重复性剪枝两者同时作用在同一段循环里。7.2 什么时候该考虑用回溯聊了这么多实现细节最后说一个更宏观的问题你怎么知道一道题该用回溯我的判断标准很简单就是三个条件同时满足问题可以分解成多步决策每一步的选择会影响后续选择。需要搜索所有可行解而不是最优解那是动态规划的活。状态空间虽然可能很大但剪枝后实际可接受。比如组合、切割、子集、排列、棋盘类天然符合这三条。而像“最长递增子序列”“最短路径”这类问题虽然也可以写成回溯但最优解交给动态规划或图算法会更高效。这个认知对新手特别重要——回溯不是万能药用错场景不仅效率低而且代码写起来很痛苦。8. 最后再分享一个实操小技巧我这几年代码面试官的经历里看到候选人挂在回溯题上的最常见原因不是没思路而是代码结构混乱。核心逻辑和剪枝条件挤在一起写着写着就晕了。我的习惯是任何回溯题都按固定顺序写四段代码参数设计想清楚 dfs 需要携带哪些状态。是 start 下标是 remain 总值是 used 数组状态越少越好能推导出来的状态就不传。终止条件必须先写。什么时候可以收割结果收割前要不要拷贝循环枚举这一步做“选择”的动作遍历当前层的所有可能性。递归与回溯递归进入下一层返回后立即撤销选择。按这个顺序写完再逐个优化剪枝条件。你会发现回溯题其实机械化程度很高真正需要动脑子的是理解问题之后如何把状态选择定义好。这个系列写到这里基础模板到进阶技巧基本覆盖完了。如果你能把 part01 的组合问题、part02 的排列子集都吃透再配合今天这篇的切割与棋盘场景刷题时遇到回溯标签的题应该能做到快速定位、标准模板、定向剪枝。接下来就是多练没有别的捷径。