回溯算法三题拆解：组合总和、去重与分割回文串的通用模板

刷LeetCode刷到Day20我的计划单上排了三条回溯题组合总和、组合总和II、分割回文串。如果你也在刷回溯大概率已经被这三道题联合“教育”过——39和40看起来像双胞胎一个允许重复选元素一个必须先排序再去重131更狡猾明明是一道字符串题切割逻辑却也要套回溯模板。把这三题放同一天练你会发现它们其实是一条主线递归撤销这套核心动作完全一致差异只在递归参数怎么传、去重逻辑怎么写、终止条件怎么定。这篇文章把三道题的完整分析、代码实现和我在调试里踩过的坑都拆开讲适合已经会递归、但还没把回溯吃透的人也适合想彻底搞明白“为什么40题非排序不可、为什么131题能当组合题做”的读者。1. 三道题一条主线回溯算法的三种形态1.1 为什么把这三题放一起练很多人刷回溯是被题单推着走今天一道明天一道做完了脑子里还是一锅粥。我的建议是把同一类考点的题放到连续几天集中刷并且最好能总结出“变与不变”。39、40、131这三题的不变是什么核心都是一个递归函数加一个for循环。递归函数负责纵向深入——在每一层解决一个子问题for循环负责横向扩展——在这一层枚举所有可能的选择。每尝试一种选择就进入下一层递归如果发现这条路走不通或者已经收集完一组答案就撤销刚才的选择回到上一层重新选。这个“选择-递归-撤销”的循环就是回溯的全部骨架。变的地方有三个递归函数的参数、进入下一层时参数的增量方式、终止条件的写法。39让我明白什么叫“可重复使用元素”此时下一层递归的起始位置依然从当前下标开始40让我理解什么叫“组合去重”必须先排序再跳过重复值131让我看到回溯不只是拿来选数字还能切割字符串只要把“选第几个元素”翻译成“切在哪里”就行。这三题做完你会得到一个特别重要的感觉回溯根本不需要背十几个不同的题解它就是一个模板套三处参数的事。1.2 先把这个模板刻进脑子里我把通用模板写在下面。这是所有组合类回溯题的底层框架后面三道题的代码都是它的变形。def backtrack(起始位置, 当前状态): if 满足终止条件: 保存当前结果 return for i in range(起始位置, 集合长度): 剪枝如果当前选择明显不合法跳过或break 做出选择更新状态 backtrack(新的起始位置, 新的状态) 撤销选择恢复状态为什么要单独强调“撤销选择”因为递归搜索本质是深度优先遍历一棵搜索树这棵树的节点之间存在共享路径。如果不撤销上一层做的选择会影响下一层的判断整个path就会越攒越多最终结果全错。你只需要记住一句话递归进去之前做了什么递归出来之后一定要原样还原。这个动作在整个回溯代码里最容易漏也是最常见的bug来源。我用走迷宫来类比回溯的思维模型。你在迷宫岔路口先选一条路往里走走到死胡同你要退回岔路口换另一条路。退回岔路口的动作就是“撤销选择”换路就是“for循环的i1”。回溯算法的代码看起来抽象但思维模型其实朴素得很。2. 组合总和LC 39最基础的回溯框架2.1 先看题目在问什么题目给一个无重复元素的整数数组candidates和一个目标数target要求找出所有可以使数字和等于target的组合。关键约束是candidates里的每个数字可以无限重复使用。比如candidates [2, 3, 6, 7]target 7答案里有[2, 2, 3]和[7]。注意[2, 3, 2]和[3, 2, 2]跟[2, 2, 3]属于同一个组合不能重复出现。这里就引出一个核心概念组合和排列的区别。组合不关心顺序[2, 2, 3]和[3, 2, 2]是同一个东西排列关心顺序这两种写法是两种不同结果。回溯算法在解组合题时必须保证枚举顺序是单调递增的索引顺序否则就会出现大量重复组合。那怎么保证不重复答案就是递归参数startIndex。在for循环里下一层递归不是从0开始而是从当前下标i开始。因为可以重复使用当前元素所以不是i1而是i。这样每一层选的数字下标永远不会小于上一层选的数字下标天然就保证了组合的单调性重复组合根本不会出现。2.2 为什么可以无限取用但要限制起点很多人第一次写39题会写成def dfs(total): for i in range(len(candidates)): ...这样写的问题不是无限递归而是会产生大量重复组合。第一层选了2第二层又可以从0开始选到2于是[2, 3]和[3, 2]都会被收集它们本质上是一个组合。标准解法用startIndex限制下一层起点效果是第一层选了2第二层可以继续选2但绝不允许回头选之前的下标。这里的“可重复选当前下标”正是39和40最大的分水岭。39题因为数字可以无限用所以进入下一层时传i而不是i1而40题每个元素只能用一次就一定要传i1。这个参数差异我建议你写在笔记本上比单纯背题解有用得多。2.3 代码实现排序加剪枝的组合拳class Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: candidates.sort() res [] path [] def dfs(startIndex, total): if total target: return if total target: res.append(path[:]) return for i in range(startIndex, len(candidates)): if total candidates[i] target: break path.append(candidates[i]) dfs(i, total candidates[i]) path.pop() dfs(0, 0) return res先排序再搜索这个细节非常重要。排序之后数组递增一旦发现total加上当前数字已经大于target那么后面所有数字都会更大全部不用看了。这时候用break直接跳出循环能砍掉大量无效递归。如果没排序就只能写成continue哪怕当前数字超了后面还可能存在更小的数字剪枝效果差很多。这里的path[:]也是细节。如果直接res.append(path)因为path是可变列表后续pop操作会把已经存入res的结果也跟着改掉。Python里列表是引用类型必须拷贝一份快照。2.4 复杂度与新手最容易踩的坑39题的时间复杂度严格推导比较麻烦因为可行解的数量和target大小、数组最小值都有关。搜索引擎给出的结论是O(S)其中S是所有可行解的长度之和这个说法学术味太重。你可以简单理解成随着target增大和候选数字变小组合数会爆炸式增长所以排序剪枝不是优化而是必需品。我踩过的坑主要有三个。第一个是忘记pop递归出来之后path越积越长收集的结果全是长长的一串。第二个是边界写错for循环的范围写成range(len(candidates))导致下一层又从头开始产生重复组合。第三个是剪枝条件放在递归函数开头用大于判断但忘记在for循环里用break提前跳出结果多跑了大量无意义的递归层。这三个坑解决之后39题基本上就稳了。但别急着庆祝40题马上会给你新的教训。3. 组合总和IILC 40去重的正确姿势3.1 题目变化有重复元素且每个只能用一次40题和39题只差两个条件candidates里可能有重复数字而且每个数字只能使用一次。比如candidates [10, 1, 2, 7, 6, 1, 5]target 8候选数组里有两个1。要求找出的组合里不能出现重复的[1, 2, 5]和[1, 7]这种重复组合。这里最让人困惑的点在于重复元素的来源有两个层次。第一个层次是同一个位置的值被不同路径重复选择比如先选下标0的1再选2和先选下标3的1再选2得到的组合都是[1, 2, 5]但因为1来自不同下标在递归树上会被当成两条不同分支。第二个层次是同一个值本身可以组成不同组合比如1和2、1和7。第二个层次是题目允许的必须保留第一个层次是题目禁止的必须去掉。3.2 排序是去重的前提没有商量余地去重之前必须先排序。为什么因为“跳过相邻重复元素”这个操作只有相同值排在一起才有效。如果数组是[1, 7, 1, 2, 5]两个1中间隔着7你很难用“当前元素和上一个元素相等”这个条件去判断。排序之后变成[1, 1, 2, 5, 7]相同值紧挨着去重逻辑就变成一句话在同一个for循环里如果当前值和前一个值相等并且前一个值已经在本层决策过就跳过当前值。排序的成本是O(n log n)和回溯本身的指数级开销相比可以忽略。所以凡是涉及去重的组合、子集、排列问题先排序永远是第一步。3.3 树层去重和树枝去重必须分清楚这是40题最核心的地方。很多教程会提到一个概念树层去重和树枝去重。所谓树层是指同一个父节点下的多个子节点分支也就是一次for循环里遍历到的不同选择所谓树枝是指沿着某一条路径往深处走的多层递归。去重针对的是树层不是树枝。举个例子candidates [1, 1, 2]target 3。第一层递归的for循环里第一个1和第二个1是树层上的两个分支。选择第一个1之后往下递归能组合出[1, 1, 2]不对应该是选择第一个1后第二层选2得到[1, 2]或者第二层选第二个1再选2得到[1, 1, 2]我重新组织一下target3时合法结果只有[1, 2]和[1, 1, 1]不对candidates里没有三个1。正确结果是[1, 2]第一层选第一个1第二层选2或者第一层选第二个1第二层选2。这两个分支得到的结果都是[1, 2]所以必须去掉一个。去重逻辑就是第一层for循环走到第二个1时发现candidates[1] candidates[0]并且前一个1已经被处理过于是continue跳过。那为什么不能跳过树枝上的重复看递归树纵向的路径第一层选了第一个1第二层for循环从startIndex1开始还可以选第二个1。这时candidates[1] candidates[0]成立但不能跳过否则就漏掉了合法的[1, 1, 2]这类组合。所以判断“前一个元素是否被使用过”需要结合它是否在当前路径上这就是used数组写法和i startIndex写法的由来。3.4 两种去重写法原理相同第一种是used数组写法class Solution: def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]: candidates.sort() res [] path [] used [False] * len(candidates) def dfs(startIndex, total): if total target: return if total target: res.append(path[:]) return for i in range(startIndex, len(candidates)): if i 0 and candidates[i] candidates[i-1] and not used[i-1]: continue if total candidates[i] target: break used[i] True path.append(candidates[i]) dfs(i 1, total candidates[i]) path.pop() used[i] False dfs(0, 0) return resused[i-1]为False代表前一个相同元素在本次分支中已经被回溯掉了也就是说当前这一个元素和上一个元素处于同一个树层。此时如果值相等当前分支得到的结果一定会和上一个分支重复所以跳过。used[i-1]为True代表前一个相同元素正在当前路径上被使用此时是树枝方向允许继续往下走。第二种是更简练的写法不需要used数组class Solution: def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]: candidates.sort() res [] path [] def dfs(startIndex, total): if total target: return if total target: res.append(path[:]) return for i in range(startIndex, len(candidates)): if i startIndex and candidates[i] candidates[i-1]: continue if total candidates[i] target: break path.append(candidates[i]) dfs(i 1, total candidates[i]) path.pop() dfs(0, 0) return resi startIndex这个条件的精髓在于在同一个for循环里i从startIndex递增当i等于startIndex时这是本层第一次枚举无论如何都不能跳过当i大于startIndex时说明前一个位置已经在本层枚举过了此时如果值相等就说明本层已经处理过相同的值直接continue。而到了下一层递归startIndex变成了i1新一层的第一个元素又满足i startIndex不会误伤树枝上的重复值。我更喜欢第二种写法理由很实际代码更短少维护一个used数组同时不需要在递归前后置位和复位降低出错概率。面试时如果能把i startIndex的真正含义讲清楚会比单纯背诵代码有说服力得多。3.5 40题提炼出的通法做完40题你可以总结一条通用规律只要题目数组里有重复元素并且要求结果不能重复先排序然后在同一层的for循环里用“当前值等于前一个值且当前下标大于本层起点”来去重。这个套路不仅适用于组合总和后面刷子集、子集II也一样适用。把这条规律记下来相当于一次性掌握一类题的解法。4. 分割回文串LC 131把切割看成组合4.1 切割问题为什么能套回溯131题给一个字符串s要求把s分割成若干子串使每个子串都是回文串返回所有可能的分割方案。比如s aab答案有两个[a, a, b]和[aa, b]。第一次看到这题的人往往会愣住回溯不是用来选数字的吗怎么跟字符串切割扯上关系这里的关键思维转换是字符串长度为n那么相邻字符之间有n-1个空隙每个空隙可以切一刀也可以不切。一个分割方案本质上就是从这n-1个空隙里选出若干个位置进行切割。这跟组合问题有什么区别组合是从一堆元素里选若干个切割是从空隙集合里选若干个。如果我把每个空隙看成一个“可以被选择的元素”那切割问题就变成了选位置的问题而选位置当然可以用回溯。这就是“一切皆可抽象成组合”的典型例子。在代码实现里startIndex代表当前段的起始位置for循环里的i代表当前段结束的位置也就是在i后面切一刀。子串s[startIndex:i1]就是切出来的这一段。确认这一段是回文之后把它加入path然后下一层递归从i1开始继续切后面的字符串。4.2 回文判断双指针和预处理判断一个字符串是不是回文双指针法最简单直接def is_palindrome(sub): left, right 0, len(sub) - 1 while left right: if sub[left] ! sub[right]: return False left 1 right - 1 return True这个判断放在递归的for循环里执行。每枚举一个i就判断s[startIndex:i1]是否为回文如果不是直接continue不需要继续往下递归。这本身就是一种高效的剪枝。如果追求性能可以提前用二维DP或记忆化搜索预处理所有子串是否是回文。比如用dp[i][j]表示s[i:j1]是否为回文状态转移是s[i] s[j]且dp[i1][j-1]为真。这样递归过程中查表O(1)就能得到结果避免反复做双指针比较。不过131题的字符串长度通常不大双指针完全够用预处理属于锦上添花。4.3 回溯切割的完整代码class Solution: def partition(self, s: str) - List[List[str]]: res [] path [] def is_palindrome(sub): left, right 0, len(sub) - 1 while left right: if sub[left] ! sub[right]: return False left 1 right - 1 return True def dfs(startIndex): if startIndex len(s): res.append(path[:]) return for i in range(startIndex, len(s)): sub s[startIndex:i1] if not is_palindrome(sub): continue path.append(sub) dfs(i 1) path.pop() dfs(0) return res终止条件不是“切完k段”而是startIndex已经走到字符串末尾。只要startIndex等于len(s)说明整个字符串被完整切完了此时path里每一段都是回文这就是一个合法分割方案。这个终止条件的逻辑和组合总和的total target是同一回事都是“当前状态已经达成目标”。4.4 切割题的细节与常见误区我在写这题时踩过的最典型的坑是试图用for循环直接从0开始切下一刀而忘记更新startIndex。比如切完[0:2]后下一刀应该从2开始如果写成dfs(i)而不是dfs(i1)就会导致同一个字符被切进多个段里产生无限递归。这里的i1和40题的i1看似一样但含义不同40题的i1是因为元素不可重复使用131题的i1是因为下一段的起点必须是当前切割点之后的位置。另一个常见误区是把回文判断放在递归内部而不是for循环内。比如先随便切割等到startIndex len(s)时才检查path是否全部回文。这样做的后果是无效分支会指数级膨胀很多明显不是回文的子串也会被一路切下去性能和代码复杂度都会变差。正确的做法是每一刀切出来就立刻检查不合格的直接剪掉让搜索树时刻保持“当前所有已切段都是回文”的状态。还有一个细节是continue和break的选择。在131题里如果当前子串不是回文不能break因为即使s[startIndex:i1]不是回文s[startIndex:i2]也可能是回文。比如aab从0开始切s[0:1]a是回文但s[0:2]aa也是回文同理s[0:1]b不行但s[0:2]bb行。所以这里必须continue继续尝试更长的子串。131题的时间复杂度最坏是O(n * 2^n)n个字符之间有n-1个空隙每个空隙有切与不切两种选择所以分割方案最多2^(n-1)种再加上每次判断回文O(n)的开销。空间复杂度主要来自递归深度O(n)。理解了这条上限你就知道为什么“提前剪枝”和“尽早判断回文”那么重要。5. 三题对比模板相同差异全在参数5.1 一张表看清三道题的差异题目元素可否重复使用数组是否排序去重方式递归参数终止条件LC 39 组合总和可以排序后剪枝无需去重dfs(i, total)total targetLC 40 组合总和II不可以必须排序i startIndex 跳过相邻重复dfs(i 1, total)total targetLC 131 分割回文串字符串不可重复切不涉及无重复问题按位置递增dfs(i 1)startIndex len(s)这张表就是我这三题的最终记忆卡片。39题的灵魂是参数传i因为可以重复取40题的灵魂是参数传i1加排序去重因为不可以重复取而且有重复值131题的灵魂是把startIndex理解为当前切割起点i理解为切割终点一切一个子串。很多解法讲解会把精力放在代码细节上但我更建议先把这张表背下来。等你面对一道陌生的回溯题先问自己三个问题这个题目求的是组合还是排列元素可不可以重复使用集合里有没有重复值这三个问题的答案直接决定递归参数怎么传以及要不要写去重。5.2 回溯代码的错误排查清单我刷回溯题时给自己列了一张排查清单每一个都亲测踩过错误类型现象解决办法忘记pop结果里出现超长path且元素重复递归返回后立即pop直接append(path)最终结果全是空列表改成res.append(path[:])或list(path)递归参数传错39题传i1漏掉重复使用方案40题传i产生重复判断“能否重复用”再定去重前没排序相邻重复判断失效统一先排序剪枝写成continue排序后无效搜索仍然很多排序后用break回文判断放最后无效切割分支指数膨胀在for循环内判断并continue我自己写回溯最常犯的是第一种和第二种。尤其是第二种Python的引用语义对新人特别不友好path在递归里被反复修改直接append进去的结果最终全部指向同一个对象。记住一个原则凡是把path存入结果集永远要拷贝一份。5.3 怎么练才会真正记住刷这三道题我不推荐上来就写代码。先做一件事把三张递归树画出来。39题选[2,3,6,7] target7画出树的第一层2、3、6、7四个分支再画第二层、第三层40题选[10,1,2,7,6,1,5] target8画出树就能看到两个1产生的重复分支长什么样131题选aab画出所有切割位置你就能直观看到为什么先判断回文能剪掉那么多分支。这三棵树画完回溯的运行机制基本就刻进脑子里了。画完树再默写代码。先默写通用模板再把39题的参数改动套上去把40题的去重套上去把131题的字符串切割思想套上去。默写几遍之后你会发现这三题本质上是同一段代码的三种状态。个人经验回溯最值钱的部分不是算法本身最后分享一点个人实战体会。回溯算法的代码量不大真正值钱的是它背后的穷举思维面对一个搜索空间很大的问题先想办法把它拆成“递归的深度”和“每一层横向的选择”然后用剪枝把无效分支尽早砍掉。这个思维不止用来刷题实际工作中排查状态机、写配置组合生成脚本、处理带约束的路径搜索都能用上同一套逻辑。我在把这些题刷完后的一个额外收获是调试回溯代码时别急着看结果用print把每次递归的path、startIndex、for循环的i都打出来观察前后顺序很快就能定位bug。记住一个铁律递归进去之前path长什么样递归出来之后path必须恢复原样你就能排查掉大部分回溯错误。如果你现在正卡在回溯上不妨照这个方法把三张树画出来先把模板默写三遍再动笔写题。磨刀不误砍柴工这三道题值得你花多一点时间。