2026/9/15 23:07:11
FEATURED · 精选文章 
刷 LeetCode 刷到中等难度时回溯法几乎是绕不过去的一道坎。我见过不少朋友卡在“单词搜索”和“分割回文串”这两道题上——不是看不懂递归而是不知道什么时候该撤销状态、什么时候该剪枝、为什么同样是回溯一道是在矩阵里走迷宫另一道却是在字符串上切缝。其实这两道题刚好展示了回溯法的两种经典形态一种是“走迷宫式”的深度优先搜索另一种是“组合枚举式”的选择分割点。把它们放在一起理解比单独刷十道题都有用之后碰到类似题型你基本一眼就能识别出该用什么套路。1. 回溯法到底是什么为什么中等题总爱考它1.1 从一棵决策树理解回溯回溯法本质上解决的是一类“搜索所有可行解”的问题。它和普通递归最大的区别在于递归只是把一个大问题拆成小问题而回溯法是在一个决策树上搜索每个节点代表一个“当前状态”从节点往下走的分支代表“下一步可以做的选择”。举一个最直观的例子你要从家走到公司每个路口都有几个方向可选。你选择一个方向走走到下一个路口发现走错了你会退回来尝试另一个方向。这个过程就是回溯。在代码里对应的事就是“递归前修改状态递归后还原状态”。这个“还原”的动作就是回溯的精髓少了它搜索状态就会互相污染导致结果千奇百怪。1.2 回溯的标准模板与两道题的定位我在实际刷题过程中总结了一个通用的回溯模板虽然不同题目细节差别很大但骨架基本一致def backtrack(状态参数): if 满足结束条件: 记录结果 return for 选择 in 当前可选的选择列表: 剪枝判断如果当前选择明显不可行则跳过 做出选择修改状态 backtrack(更新后的状态参数) 撤销选择还原状态“单词搜索”和“分割回文串”都是中等难度里非常标准的回溯题但它们的搜索结构完全不同“单词搜索”是在一个完全给定的二维网格里做路径搜索属于走迷宫型。它的状态参数是“当前所在坐标”和“已匹配到第几个字符”选择列表是上下左右四个方向。“分割回文串”是在一个一维字符串上枚举切割方案属于组合切割型。它的状态参数是“当前处理到字符串的哪个位置”选择列表是“切割出多长的前缀子串”。抓住这个区别你就能理解为什么这两道题经常在面试题单里被放在一起——它们互补地展示了回溯法在不同数据结构上的应用。1.3 回溯和 DFS、递归到底是什么关系这三个概念经常混在一起我直接说我的理解递归是工具的底座所有回溯代码都是用递归函数写成的DFS 是一种搜索策略即在状态空间中优先往深处探索回溯法是 DFS 的一种应用它的特点是“搜索所有解”且在搜索过程中需要“恢复现场”。所以你也可以认为回溯法 DFS 状态撤销。这个认知非常重要因为很多新手写回溯时只写了递归和判断忘了撤销结果代码跑起来莫名其妙。2. 单词搜索二维矩阵里的 DFS、visited 与剪枝2.1 题目逻辑为什么需要遍历所有格子作为起点题目给一个二维字符网格 board 和一个单词 word问 word 是否存在于网格中。所谓“存在”指的是单词中的字母在网格中按相邻顺序连成一条路径而且同一个格子不能重复使用。我第一次做这道题时犯的一个思路错误是想着能不能用一个简单的双循环配条件判断来匹配。后来发现完全不行因为当前格子匹配上之后下一步可能往四个方向走每个方向又是一个新的匹配问题。这明显适合用 DFS 去排查所有路径。另一个要点是单词的起点并不固定。你事先并不知道 word 的第一个字符会出现在哪个格子里所以主函数必然要遍历整个矩阵把每个格子都当作潜在的起点去尝试。class Solution: def exist(self, board: List[List[str]], word: str) - bool: m, n len(board), len(board[0]) visited [[False] * n for _ in range(m)] dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(x: int, y: int, idx: int) - bool: if idx len(word): return True if not (0 x m and 0 y n): return False if visited[x][y] or board[x][y] ! word[idx]: return False visited[x][y] True for dx, dy in dirs: if dfs(x dx, y dy, idx 1): return True visited[x][y] False return False for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False这段代码的核心思路我已经写在注释里了下面拆开讲几个容易出错的细节。2.2 方向数组与 visited 的还原时机方向数组写成[(1,0),(-1,0),(0,1),(0,-1)]是最清晰的做法别图省事用 8 个方向那是另一种题型的玩法。每一步从当前格子出发只走上下左右四邻域。边界检查我习惯放在递归函数的最前面。这个顺序看似无关实际上很有讲究如果把if board[x][y] ! word[idx]放在边界检查之前当坐标越界时访问board[x][y]会直接抛异常。所以要么先判边界要么用 Python 中0 x m的连写形式做短路判断。visited 数组用来防止同一个格子被重复使用。这里有一个新手非常容易踩的坑为什么要在递归返回前把 visited[x][y] 重新设为 False因为 visited 记录的是“当前搜索路径上”已访问的格子而不是“所有历史路径上的访问记录”。如果这个格子在这条路径上走不通下一次换一个起点或者换一种走法时它应该可以被重新访问。撤销这个标记本质上是把状态恢复到递归前的样子这正是回溯法最核心的“恢复现场”。2.3 字符串匹配顺序与短路运算的妙用很多讲解会直接写if board[x][y] ! word[idx] or visited[x][y]但是把visited放在前面其实是更好的实践。原因很简单如果格子已经访问过那么访问board[x][y]这个字符内容其实已经没意义了没必要再做一次字符比较。反过来先比较字符时即使字符匹配失败也得多做一次visited读取。虽然这种性能差异在一个小矩阵上可以忽略不计但养成把“最快能淘汰的选择放前面”的习惯对后续刷更大数据量的题目帮助很大。另外注意结束条件的顺序if idx len(word)必须在边界检查之前。因为当最后一个字符匹配成功时我们会在递归里传入idx 1此时已经不需要再判断坐标是否越界了直接返回 True 代表整条路径已经找完。2.4 单词搜索的剪枝点与复杂度估算单词搜索的剪枝集中在“字符不匹配”这个判断上。当一个格子不等于 word 中对应位置的字符时它下面的整棵子树都无需探索这就是我最常用的可行性剪枝。复杂度方面设单词长度为 L网格大小为 M×N。外层需要遍历所有格子作为起点复杂度是 M×N。每一步搜索最多有四个方向但因为 visited 的存在之后不能再走回上一个格子所以从第二步开始最多只有 3 个方向。最坏时间复杂度约为 O(M × N × 4 × 3^(L-1))也就是 O(M × N × 3^L)。空间复杂度主要来自递归栈的深度和 visited 数组都是 O(L M×N)可以视为 O(M×N)。这里有个有意思的地方当 L 远大于 M×N 时理论上搜索空间应该变小因为路径长度受格子总数限制。LeetCode 的测试用例里也有这种边界情况实际跑起来反而比理论上限快很多。3. 分割回文串切割点枚举与回文预判的取舍3.1 把“分割”翻译成回溯的语言“分割回文串”要求把字符串 s 分割成若干子串使得每个子串都是回文串返回所有可能的分割方案。学过回溯的人一看就知道要用回溯但新手容易卡在“怎么把一个字符串切出所有方案”上。我的建议是不要想着物理上切切切而是把它抽象成“在一个长度为 n 的字符串上选择若干个切割点”。选择切割点的过程可以用递归来模拟。假设当前已经处理到字符串的 start 位置下一步我可以选择让s[start:end]作为一个子串只要这个子串是回文。其中 end 可以从 start 一直取到 n-1每个合法的 end 都代表一种选择。每当走到 start n 时说明整个字符串已经被切完了当前方案记入结果。如果把这个过程画成一棵树根节点是start0每个节点的子节点是“当前从 start 开始的所有合法回文前缀”整棵树高度不超过 n。这也是为什么这道题的搜索空间非常直观。3.2 回文判断的两种做法双指针与 DP 预计算判断一个子串是不是回文最朴素的做法是双指针def is_palindrome(sub: str) - bool: l, r 0, len(sub) - 1 while l r: if sub[l] ! sub[r]: return False l 1 r - 1 return True这种方法在“分割回文串 I”里完全能过因为总方案数不大。但有一个细节让我觉得必须聊一下在回溯过程中你会反复调用is_palindrome同一个子串可能被判断很多次造成大量重复计算。更优雅的做法是先用动态规划预处理一个二维布尔数组 dp其中dp[i][j]表示s[i:j1]是否是回文串。有了这个表回溯时只需要 O(1) 时间就能完成判断。n len(s) dp [[False] * n for _ in range(n)] for j in range(n): for i in range(j 1): if s[i] s[j] and (j - i 2 or dp[i 1][j - 1]): dp[i][j] True这个 DP 的递推关系需要细说一个子串s[i:j1]是回文当且仅当两端字符相等并且去掉两端后内部的子串也是回文。当j - i 2时说明子串长度是 1、2 或 3此时只要两端字符相等内部自然是回文不需要依赖更小的子串。循环方向也必须注意外层从小到大枚举右端 j内层枚举左端 i。这样才能保证计算dp[i][j]时dp[i1][j-1]已经被计算过。如果反过来枚举dp[i1][j-1]可能还没有结果递推就失效了。3.3 分割回文串的完整回溯代码用 DP 预计算整个回溯代码非常干净class Solution: def partition(self, s: str) - List[List[str]]: n len(s) dp [[False] * n for _ in range(n)] for j in range(n): for i in range(j 1): if s[i] s[j] and (j - i 2 or dp[i 1][j - 1]): dp[i][j] True res [] path [] def backtrack(start: int): if start n: res.append(path[:]) return for end in range(start, n): if dp[start][end]: path.append(s[start:end 1]) backtrack(end 1) path.pop() backtrack(0) return res注意res.append(path[:])这里的切片拷贝。直接用res.append(path)会让结果列表里所有元素指向同一个列表对象最后回溯撤销时会把已经记录的结果也一并改掉。这个错误我记得自己第一次写的时候也犯过排查了很久。3.4 分割回文串的复杂度与优化方向最坏情况下比如字符串由同一个字符组成那么任意切割方案都合法方案总数是 2^(n-1)。每个方案都要在结果里保存一份长度为 n 的列表所以时间复杂度是 O(n × 2^(n-1))空间复杂度主要是递归栈和结果存储。如果只要判断能否分割而不是返回所有方案那就要用动态规划做“分割回文串 II”求最少切割次数那是完全不同的思路不需要回溯。区分这两种问法很重要面试官经常在这两个变体之间切换来考察你对问题本质的理解。另外还有一个工程层面的优化如果觉得二维 DP 数组太占空间可以改为dp[i]表示s[i:j1]的滚动状态但因为回溯本身的空间消耗已经是指数级预计算的二维数组通常不是瓶颈。我一般是能写清楚优先不在这种地方做无谓的节省。4. 两道题放在一起看回溯模板的两种形态4.1 单词搜索与分割回文串的形态对比把两道题并排放你就能看出回溯法在不同数据形态下的差异对比维度单词搜索分割回文串数据结构二维矩阵一维字符串搜索空间路径格子序列切割方案子串组合状态参数当前坐标 (x, y) 已匹配字符数 idx当前处理到的位置 start选择列表上下左右四个方向从 start 到 n-1 的所有 end状态修改标记 visited[x][y] True把子串加入 path 列表状态撤销标记 visited[x][y] Falsepath.pop()剪枝依据字符是否匹配子串是否为回文终止条件idx len(word)start n这个对比表能直接套在几乎所有回溯题上。你下次遇到新题先问自己三个问题状态参数是什么选择列表是什么什么时候撤销4.2 为什么“撤销”这一步不能省我见过太多人死记回溯模板知道要写“撤销”但不知道为什么写。如果不理解迟早会在复杂的题里翻车。回溯搜索的是所有方案所以它在递归返回时要保证“环境”和递归之前完全一样。单词搜索里如果不把visited[x][y]还原那么某条路径走到死胡同后其他路径再进入这个格子时会被误判为“已访问”导致漏解。分割回文串里如果不path.pop()那当前选择会污染到兄弟节点本来只包含 a、b 两个子串的方案会莫名其妙多出之前路径上的残留字符。用生活语言说就是你从书架拿了一本书翻了几页发现不需要把它放回原位才能继续拿下一本。不放回去书架就乱了后面的操作全都会错。4.3 剪枝回溯的性能命脉纯回溯是指数级复杂度剪枝是让它可用的关键。两道题的剪枝都属于“可行性剪枝”即在进入某条分支之前判断它是否可能产生解。但剪枝的位置和形式差别很大单词搜索是“当前格子的字符和预期不匹配就直接返回 False”剪枝发生在进入下一步方向之前分割回文串是“当前子串不是回文就跳过这个 end”剪枝发生在枚举 end 的循环体内部。我把剪枝原则总结成一句话在所有可能的失败信号里选择最快能检测到的那一个放在最前面判断。你不需要一次把所有剪枝都写完美先保证正确性再根据超时情况逐步加条件。LeetCode 的中等题一般验证逻辑正确性就够了剪枝往往只是为了跑得更快。5. 实战踩坑刷这两道题时我犯过的错和调整思路5.1 高频错误清单第一类错误和 visited 有关。新手最容易写错的是把 visited 放在了递归函数外然后全局共享却忘了在“一条路径走完”之后重置。更隐蔽的错误是在某个分支返回 True 后没有还原 visited——这其实不影响正确性因为整个函数已经要返回 True 了但这种写法一旦调整代码结构就会出问题。我建议任何时候都保持“递归前修改、递归后撤销”的对称写法从根上避免隐患。第二类错误是分割回文串里的引用拷贝问题。前面提到过res.append(path)这种写法会让答案中所有元素变成同一个列表对象结果输出会是一堆相同的列表。LeetCode 的测试集里这个错误非常明显但 IDE 里单步调试时容易忽略。记住记录结果时永远考虑是否需要拷贝。第三类是参数传递错误。单词搜索中 idx 的更新写成dfs(x dx, y dy, idx 1)有人会不小心写成了dfs(x dx, y dy, idx)这在 Python 里是不合法的但在 C 或 Java 里会造成“先传值再自增”的奇怪行为导致永远匹配第 0 个字符。我是吃过这个亏的后来都统一用idx 1这种不修改变量本身的方式。5.2 调试技巧小用例与手工推演我刷回溯题时的调试顺序是固定的先手工画一棵递归树。不要偷懒尤其是第一次做这类题时。画一次“aab”的分割过程比看十遍代码都有效。然后用最小用例跑代码。比如单词搜索用board [[a]], word a分割回文串用s a确认最简路径能通。出现问题后在递归入口打印当前状态参数。单词搜索打印x, y, idx和 visited 矩阵的变化分割回文串打印start和 path 当前内容。看到状态错乱的位置问题根源通常会立刻暴露。还有一个小技巧遇到“答案重复”问题多半是同一个方案从不同路径被构造出来了考虑加start参数改变选择列表来避免重复。这两道题本身不会触发这种问题但同套路的“组合总和 II”就会先有这个意识后面学得更顺。5.3 从这两道题延伸出去的相关变体既然热搜词里有“LeetCode 热门 100 题”我就顺便划一下重点。单词搜索这个套路可以直接迁移到“岛屿数量”DFS 遍历矩阵、“最大岛屿面积”DFS 计数、“矩阵中最长递增路径”DFS 记忆化。这些题的核心都是矩阵遍历只是状态转移条件和返回值不同。分割回文串的套路则可以迁移到“组合总和”、“子集”、“全排列”这一组经典回溯题。它们都是在一维结构上枚举选择区别只在于“选择列表是否允许重复元素”和“结果是否讲究顺序”。把这组题放在一起刷你对回溯的理解会上一个台阶。另外 LeetCode 周赛里经常出现这两道题的杂交版本比如“在矩阵中找到单词且路径不能交叉”的变体。本质上就是在单词搜索的代码里多维护一个路径集合剪枝条件更严格而已。基础模板掌握扎实了这些变体其实就是叠 Buff不会有特别大的跳跃感。我自己刷这两道题时最深的体会是回溯不能硬背模板要想清楚每个变量在递归树里代表什么。单词搜索里的 idx 代表树的深度矩阵坐标代表当前节点分割回文串里的 start 代表剩余字符串的起点path 代表从根到当前节点的路径记录。把这些角色搞清楚撤销和剪枝就不再是玄学而是顺理成章的事。最后分享一个我的个人习惯写回溯代码前先去白板上画递归树画完再编码。这样看起来慢实际调试时间会省一大半。你可以拿这两道题试试体会一下“画完之后代码自然就出来了”的感觉。
回溯法实战：从单词搜索到分割回文串的模板与剪枝
刷 LeetCode 刷到中等难度时回溯法几乎是绕不过去的一道坎。我见过不少朋友卡在“单词搜索”和“分割回文串”这两道题上——不是看不懂递归而是不知道什么时候该撤销状态、什么时候该剪枝、为什么同样是回溯一道是在矩阵里走迷宫另一道却是在字符串上切缝。其实这两道题刚好展示了回溯法的两种经典形态一种是“走迷宫式”的深度优先搜索另一种是“组合枚举式”的选择分割点。把它们放在一起理解比单独刷十道题都有用之后碰到类似题型你基本一眼就能识别出该用什么套路。1. 回溯法到底是什么为什么中等题总爱考它1.1 从一棵决策树理解回溯回溯法本质上解决的是一类“搜索所有可行解”的问题。它和普通递归最大的区别在于递归只是把一个大问题拆成小问题而回溯法是在一个决策树上搜索每个节点代表一个“当前状态”从节点往下走的分支代表“下一步可以做的选择”。举一个最直观的例子你要从家走到公司每个路口都有几个方向可选。你选择一个方向走走到下一个路口发现走错了你会退回来尝试另一个方向。这个过程就是回溯。在代码里对应的事就是“递归前修改状态递归后还原状态”。这个“还原”的动作就是回溯的精髓少了它搜索状态就会互相污染导致结果千奇百怪。1.2 回溯的标准模板与两道题的定位我在实际刷题过程中总结了一个通用的回溯模板虽然不同题目细节差别很大但骨架基本一致def backtrack(状态参数): if 满足结束条件: 记录结果 return for 选择 in 当前可选的选择列表: 剪枝判断如果当前选择明显不可行则跳过 做出选择修改状态 backtrack(更新后的状态参数) 撤销选择还原状态“单词搜索”和“分割回文串”都是中等难度里非常标准的回溯题但它们的搜索结构完全不同“单词搜索”是在一个完全给定的二维网格里做路径搜索属于走迷宫型。它的状态参数是“当前所在坐标”和“已匹配到第几个字符”选择列表是上下左右四个方向。“分割回文串”是在一个一维字符串上枚举切割方案属于组合切割型。它的状态参数是“当前处理到字符串的哪个位置”选择列表是“切割出多长的前缀子串”。抓住这个区别你就能理解为什么这两道题经常在面试题单里被放在一起——它们互补地展示了回溯法在不同数据结构上的应用。1.3 回溯和 DFS、递归到底是什么关系这三个概念经常混在一起我直接说我的理解递归是工具的底座所有回溯代码都是用递归函数写成的DFS 是一种搜索策略即在状态空间中优先往深处探索回溯法是 DFS 的一种应用它的特点是“搜索所有解”且在搜索过程中需要“恢复现场”。所以你也可以认为回溯法 DFS 状态撤销。这个认知非常重要因为很多新手写回溯时只写了递归和判断忘了撤销结果代码跑起来莫名其妙。2. 单词搜索二维矩阵里的 DFS、visited 与剪枝2.1 题目逻辑为什么需要遍历所有格子作为起点题目给一个二维字符网格 board 和一个单词 word问 word 是否存在于网格中。所谓“存在”指的是单词中的字母在网格中按相邻顺序连成一条路径而且同一个格子不能重复使用。我第一次做这道题时犯的一个思路错误是想着能不能用一个简单的双循环配条件判断来匹配。后来发现完全不行因为当前格子匹配上之后下一步可能往四个方向走每个方向又是一个新的匹配问题。这明显适合用 DFS 去排查所有路径。另一个要点是单词的起点并不固定。你事先并不知道 word 的第一个字符会出现在哪个格子里所以主函数必然要遍历整个矩阵把每个格子都当作潜在的起点去尝试。class Solution: def exist(self, board: List[List[str]], word: str) - bool: m, n len(board), len(board[0]) visited [[False] * n for _ in range(m)] dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(x: int, y: int, idx: int) - bool: if idx len(word): return True if not (0 x m and 0 y n): return False if visited[x][y] or board[x][y] ! word[idx]: return False visited[x][y] True for dx, dy in dirs: if dfs(x dx, y dy, idx 1): return True visited[x][y] False return False for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False这段代码的核心思路我已经写在注释里了下面拆开讲几个容易出错的细节。2.2 方向数组与 visited 的还原时机方向数组写成[(1,0),(-1,0),(0,1),(0,-1)]是最清晰的做法别图省事用 8 个方向那是另一种题型的玩法。每一步从当前格子出发只走上下左右四邻域。边界检查我习惯放在递归函数的最前面。这个顺序看似无关实际上很有讲究如果把if board[x][y] ! word[idx]放在边界检查之前当坐标越界时访问board[x][y]会直接抛异常。所以要么先判边界要么用 Python 中0 x m的连写形式做短路判断。visited 数组用来防止同一个格子被重复使用。这里有一个新手非常容易踩的坑为什么要在递归返回前把 visited[x][y] 重新设为 False因为 visited 记录的是“当前搜索路径上”已访问的格子而不是“所有历史路径上的访问记录”。如果这个格子在这条路径上走不通下一次换一个起点或者换一种走法时它应该可以被重新访问。撤销这个标记本质上是把状态恢复到递归前的样子这正是回溯法最核心的“恢复现场”。2.3 字符串匹配顺序与短路运算的妙用很多讲解会直接写if board[x][y] ! word[idx] or visited[x][y]但是把visited放在前面其实是更好的实践。原因很简单如果格子已经访问过那么访问board[x][y]这个字符内容其实已经没意义了没必要再做一次字符比较。反过来先比较字符时即使字符匹配失败也得多做一次visited读取。虽然这种性能差异在一个小矩阵上可以忽略不计但养成把“最快能淘汰的选择放前面”的习惯对后续刷更大数据量的题目帮助很大。另外注意结束条件的顺序if idx len(word)必须在边界检查之前。因为当最后一个字符匹配成功时我们会在递归里传入idx 1此时已经不需要再判断坐标是否越界了直接返回 True 代表整条路径已经找完。2.4 单词搜索的剪枝点与复杂度估算单词搜索的剪枝集中在“字符不匹配”这个判断上。当一个格子不等于 word 中对应位置的字符时它下面的整棵子树都无需探索这就是我最常用的可行性剪枝。复杂度方面设单词长度为 L网格大小为 M×N。外层需要遍历所有格子作为起点复杂度是 M×N。每一步搜索最多有四个方向但因为 visited 的存在之后不能再走回上一个格子所以从第二步开始最多只有 3 个方向。最坏时间复杂度约为 O(M × N × 4 × 3^(L-1))也就是 O(M × N × 3^L)。空间复杂度主要来自递归栈的深度和 visited 数组都是 O(L M×N)可以视为 O(M×N)。这里有个有意思的地方当 L 远大于 M×N 时理论上搜索空间应该变小因为路径长度受格子总数限制。LeetCode 的测试用例里也有这种边界情况实际跑起来反而比理论上限快很多。3. 分割回文串切割点枚举与回文预判的取舍3.1 把“分割”翻译成回溯的语言“分割回文串”要求把字符串 s 分割成若干子串使得每个子串都是回文串返回所有可能的分割方案。学过回溯的人一看就知道要用回溯但新手容易卡在“怎么把一个字符串切出所有方案”上。我的建议是不要想着物理上切切切而是把它抽象成“在一个长度为 n 的字符串上选择若干个切割点”。选择切割点的过程可以用递归来模拟。假设当前已经处理到字符串的 start 位置下一步我可以选择让s[start:end]作为一个子串只要这个子串是回文。其中 end 可以从 start 一直取到 n-1每个合法的 end 都代表一种选择。每当走到 start n 时说明整个字符串已经被切完了当前方案记入结果。如果把这个过程画成一棵树根节点是start0每个节点的子节点是“当前从 start 开始的所有合法回文前缀”整棵树高度不超过 n。这也是为什么这道题的搜索空间非常直观。3.2 回文判断的两种做法双指针与 DP 预计算判断一个子串是不是回文最朴素的做法是双指针def is_palindrome(sub: str) - bool: l, r 0, len(sub) - 1 while l r: if sub[l] ! sub[r]: return False l 1 r - 1 return True这种方法在“分割回文串 I”里完全能过因为总方案数不大。但有一个细节让我觉得必须聊一下在回溯过程中你会反复调用is_palindrome同一个子串可能被判断很多次造成大量重复计算。更优雅的做法是先用动态规划预处理一个二维布尔数组 dp其中dp[i][j]表示s[i:j1]是否是回文串。有了这个表回溯时只需要 O(1) 时间就能完成判断。n len(s) dp [[False] * n for _ in range(n)] for j in range(n): for i in range(j 1): if s[i] s[j] and (j - i 2 or dp[i 1][j - 1]): dp[i][j] True这个 DP 的递推关系需要细说一个子串s[i:j1]是回文当且仅当两端字符相等并且去掉两端后内部的子串也是回文。当j - i 2时说明子串长度是 1、2 或 3此时只要两端字符相等内部自然是回文不需要依赖更小的子串。循环方向也必须注意外层从小到大枚举右端 j内层枚举左端 i。这样才能保证计算dp[i][j]时dp[i1][j-1]已经被计算过。如果反过来枚举dp[i1][j-1]可能还没有结果递推就失效了。3.3 分割回文串的完整回溯代码用 DP 预计算整个回溯代码非常干净class Solution: def partition(self, s: str) - List[List[str]]: n len(s) dp [[False] * n for _ in range(n)] for j in range(n): for i in range(j 1): if s[i] s[j] and (j - i 2 or dp[i 1][j - 1]): dp[i][j] True res [] path [] def backtrack(start: int): if start n: res.append(path[:]) return for end in range(start, n): if dp[start][end]: path.append(s[start:end 1]) backtrack(end 1) path.pop() backtrack(0) return res注意res.append(path[:])这里的切片拷贝。直接用res.append(path)会让结果列表里所有元素指向同一个列表对象最后回溯撤销时会把已经记录的结果也一并改掉。这个错误我记得自己第一次写的时候也犯过排查了很久。3.4 分割回文串的复杂度与优化方向最坏情况下比如字符串由同一个字符组成那么任意切割方案都合法方案总数是 2^(n-1)。每个方案都要在结果里保存一份长度为 n 的列表所以时间复杂度是 O(n × 2^(n-1))空间复杂度主要是递归栈和结果存储。如果只要判断能否分割而不是返回所有方案那就要用动态规划做“分割回文串 II”求最少切割次数那是完全不同的思路不需要回溯。区分这两种问法很重要面试官经常在这两个变体之间切换来考察你对问题本质的理解。另外还有一个工程层面的优化如果觉得二维 DP 数组太占空间可以改为dp[i]表示s[i:j1]的滚动状态但因为回溯本身的空间消耗已经是指数级预计算的二维数组通常不是瓶颈。我一般是能写清楚优先不在这种地方做无谓的节省。4. 两道题放在一起看回溯模板的两种形态4.1 单词搜索与分割回文串的形态对比把两道题并排放你就能看出回溯法在不同数据形态下的差异对比维度单词搜索分割回文串数据结构二维矩阵一维字符串搜索空间路径格子序列切割方案子串组合状态参数当前坐标 (x, y) 已匹配字符数 idx当前处理到的位置 start选择列表上下左右四个方向从 start 到 n-1 的所有 end状态修改标记 visited[x][y] True把子串加入 path 列表状态撤销标记 visited[x][y] Falsepath.pop()剪枝依据字符是否匹配子串是否为回文终止条件idx len(word)start n这个对比表能直接套在几乎所有回溯题上。你下次遇到新题先问自己三个问题状态参数是什么选择列表是什么什么时候撤销4.2 为什么“撤销”这一步不能省我见过太多人死记回溯模板知道要写“撤销”但不知道为什么写。如果不理解迟早会在复杂的题里翻车。回溯搜索的是所有方案所以它在递归返回时要保证“环境”和递归之前完全一样。单词搜索里如果不把visited[x][y]还原那么某条路径走到死胡同后其他路径再进入这个格子时会被误判为“已访问”导致漏解。分割回文串里如果不path.pop()那当前选择会污染到兄弟节点本来只包含 a、b 两个子串的方案会莫名其妙多出之前路径上的残留字符。用生活语言说就是你从书架拿了一本书翻了几页发现不需要把它放回原位才能继续拿下一本。不放回去书架就乱了后面的操作全都会错。4.3 剪枝回溯的性能命脉纯回溯是指数级复杂度剪枝是让它可用的关键。两道题的剪枝都属于“可行性剪枝”即在进入某条分支之前判断它是否可能产生解。但剪枝的位置和形式差别很大单词搜索是“当前格子的字符和预期不匹配就直接返回 False”剪枝发生在进入下一步方向之前分割回文串是“当前子串不是回文就跳过这个 end”剪枝发生在枚举 end 的循环体内部。我把剪枝原则总结成一句话在所有可能的失败信号里选择最快能检测到的那一个放在最前面判断。你不需要一次把所有剪枝都写完美先保证正确性再根据超时情况逐步加条件。LeetCode 的中等题一般验证逻辑正确性就够了剪枝往往只是为了跑得更快。5. 实战踩坑刷这两道题时我犯过的错和调整思路5.1 高频错误清单第一类错误和 visited 有关。新手最容易写错的是把 visited 放在了递归函数外然后全局共享却忘了在“一条路径走完”之后重置。更隐蔽的错误是在某个分支返回 True 后没有还原 visited——这其实不影响正确性因为整个函数已经要返回 True 了但这种写法一旦调整代码结构就会出问题。我建议任何时候都保持“递归前修改、递归后撤销”的对称写法从根上避免隐患。第二类错误是分割回文串里的引用拷贝问题。前面提到过res.append(path)这种写法会让答案中所有元素变成同一个列表对象结果输出会是一堆相同的列表。LeetCode 的测试集里这个错误非常明显但 IDE 里单步调试时容易忽略。记住记录结果时永远考虑是否需要拷贝。第三类是参数传递错误。单词搜索中 idx 的更新写成dfs(x dx, y dy, idx 1)有人会不小心写成了dfs(x dx, y dy, idx)这在 Python 里是不合法的但在 C 或 Java 里会造成“先传值再自增”的奇怪行为导致永远匹配第 0 个字符。我是吃过这个亏的后来都统一用idx 1这种不修改变量本身的方式。5.2 调试技巧小用例与手工推演我刷回溯题时的调试顺序是固定的先手工画一棵递归树。不要偷懒尤其是第一次做这类题时。画一次“aab”的分割过程比看十遍代码都有效。然后用最小用例跑代码。比如单词搜索用board [[a]], word a分割回文串用s a确认最简路径能通。出现问题后在递归入口打印当前状态参数。单词搜索打印x, y, idx和 visited 矩阵的变化分割回文串打印start和 path 当前内容。看到状态错乱的位置问题根源通常会立刻暴露。还有一个小技巧遇到“答案重复”问题多半是同一个方案从不同路径被构造出来了考虑加start参数改变选择列表来避免重复。这两道题本身不会触发这种问题但同套路的“组合总和 II”就会先有这个意识后面学得更顺。5.3 从这两道题延伸出去的相关变体既然热搜词里有“LeetCode 热门 100 题”我就顺便划一下重点。单词搜索这个套路可以直接迁移到“岛屿数量”DFS 遍历矩阵、“最大岛屿面积”DFS 计数、“矩阵中最长递增路径”DFS 记忆化。这些题的核心都是矩阵遍历只是状态转移条件和返回值不同。分割回文串的套路则可以迁移到“组合总和”、“子集”、“全排列”这一组经典回溯题。它们都是在一维结构上枚举选择区别只在于“选择列表是否允许重复元素”和“结果是否讲究顺序”。把这组题放在一起刷你对回溯的理解会上一个台阶。另外 LeetCode 周赛里经常出现这两道题的杂交版本比如“在矩阵中找到单词且路径不能交叉”的变体。本质上就是在单词搜索的代码里多维护一个路径集合剪枝条件更严格而已。基础模板掌握扎实了这些变体其实就是叠 Buff不会有特别大的跳跃感。我自己刷这两道题时最深的体会是回溯不能硬背模板要想清楚每个变量在递归树里代表什么。单词搜索里的 idx 代表树的深度矩阵坐标代表当前节点分割回文串里的 start 代表剩余字符串的起点path 代表从根到当前节点的路径记录。把这些角色搞清楚撤销和剪枝就不再是玄学而是顺理成章的事。最后分享一个我的个人习惯写回溯代码前先去白板上画递归树画完再编码。这样看起来慢实际调试时间会省一大半。你可以拿这两道题试试体会一下“画完之后代码自然就出来了”的感觉。 
