回溯算法通用模板：组合总和与分割回文串刷题笔记

刷题打卡到第20天的时候，我给自己安排了一个小高潮：LeetCode 的 39. 组合总和、40. 组合总和II、131. 分割回文串。三道题表面上形态完全不一样，两个是数组题目，一个是字符串题目，但仔细一拆就会发现，它们练的是同一套东西——回溯算法。组合总和解决的是“可以重复选数怎么枚举”，组合总和II加了一个最难缠的“重复值去重”，分割回文串则是把“从容器里挑元素”换成了“从字符串里切片段”。把这些变形放在同一天刷，比单独刷十道编号飘忽的题有效得多。

这篇文章我会直接按我自己的刷题顺序来写：先讲为什么三道题可以共用同一个模板，再分别拆解每一题的关键决策，最后把三份代码放在一起对比，顺带把我调试时踩过的坑都交代清楚。

1. 三道题放在一起刷的真正原因：它们共享同一套回溯模板

1.1 回溯的本质是“递归加回退”

很多人一提回溯就感觉很高深，其实它就是一个带撤销功能的穷举过程。它的核心是在一棵多叉树上做深度优先搜索：先沿着一条路走到头，看看这条路的终点是不是答案，如果是就记录下来；如果不是或者明显没戏，就回退一个节点，换另一条路继续走。这个“回退”动作，就是回溯和普通递归最不一样的地方。

我习惯用一个生活化的类比：想象你站在一排货架前面，需要从里面挑几个商品，凑出一个指定的总价。你伸手拿了一个商品放到购物篮里，接着继续看后面的货架；如果后面怎么挑都凑不出目标价格，你就把刚才那个商品放回货架，再换下一个商品试。这个“放回货架”的动作，放到代码里就是path.pop()。

理解了这个框架，再看 LeetCode 这三道中等题，就会发现它们的代码只有几个变量在变。

1.2 我总结出的万能回溯代码骨架

我刷题到第20天的时候，把标准回溯模板压缩成了这样一个结构：

def dfs(start, path, ...): if 满足某个结束条件: res.append(path[:]) return for i in range(start, n): if 可以提前剪枝: break 或 continue path.append(第i项) dfs(下一个起点, path, 状态更新) path.pop()

这个模板是三段式的：

• 第一段是递归出口，判断当前path是否已经构成一组有效答案；
• 第二段是遍历当前可用的选择，这是回溯题的灵魂所在；
• 第三段是撤销选择，让路径重新变干净，方便下一次尝试。

三道题都百分之百符合这个模板，差别只是三个点：当前可选择的集合是什么、选择完以后下一层起点怎么变、需不需要加额外的去重条件。

1.3 三道题的差异其实只有三处

先用一个简单表格说明差异在哪里：

这三处差异是互相独立的。比如“元素能不能重复使用”，直观上只影响递归起点；而“候选数组里有没有重复值”，影响的是要不要加去重条件。我用这个视角刷题之后，遇到陌生题目第一反应就不再是“这道题是什么算法”，而是“这个选择的起点应该怎么变、去重条件放在哪里”。这个思维转换，我觉得是 Day20 最大的收获。

2. 39. 组合总和：先把“可重复选数”的搜索树走明白

2.1 无限次取同一个数的本质，就是下一层从 i 开始

39 题的要求是：给一个无重复元素的候选数组，比如[2,3,6,7]，再给一个目标值7，找出所有和为目标值的组合，同一个数字可以无限次重复使用。

第一眼看到“无限次”很多人会慌，觉得搜索空间是不是无穷的。但其实只要候选数字都是正整数，复杂度就是有限的：每个数字不是无限次真的被选到无穷个，而是“是否能再次选择同一个下标”的问题。

关键就在递归入参。如果下一层递归仍然从i开始，那当前数字就能再次被选；如果下一层从i+1开始，那当前数字就用不到了。所谓“无限次重复”，落实成代码就是一个参数的变化。

而startIndex这个参数同时还有一个作用：防止出现[2,3]和[3,2]这样顺序不同但内容相同的组合。组合问题不看顺序，如果我们每次都从头扫描，那么先选 2 再选 3，和先选 3 再选 2，会被当成两个答案。规定递归只能从当前下标或更后面开始，就能保证路径里的数字始终是非递减的下标序列，从而屏蔽所有交换顺序造成的重复。

用[2,3,6,7]举例。第一层遍历的是 2、3、6、7；选了 2 之后，下一层依然从 2 开始，于是会出现[2,2,3]这种组合，但绝不会出现[3,2,2]，因为选 3 的分支不可能回头去取下标比 3 更靠前的 2。

2.2 递归函数参数怎么设计才不容易乱

我最终写成的递归函数是这样的：

def combinationSum(candidates, target): candidates.sort() res = [] def dfs(start, path, total): if total == target: res.append(path[:]) return if total > target: return for i in range(start, len(candidates)): if total + candidates[i] > target: break path.append(candidates[i]) dfs(i, path, total + candidates[i]) path.pop() dfs(0, [], 0) return res

三个参数start、path、total各有各的用途：start表示这一层可以扫描的下标起点，path是当前已经积攒的组合，total是 path 当前数字的和。相比维护一个sum变量然后在递归回来后减掉，直接在递归传参时用total + candidates[i]会更简洁，不用再费心去恢复现场。

递归出口我写了两行。第一个是total == target，这说明当前组合正好凑齐，把path的快照存入结果；第二个是total > target，说明已经超了，当前分支没意义，直接返回。

2.3 剪枝为什么敢用 break，而不是 continue

不知道你有没有过这个困惑：为什么这里是if total + candidates[i] > target: break，而不是continue？

这两个语句的区别在于跳出层级。continue只是跳过当前这个数，继续看后面的数；break是直接终止整个 for 循环。两者之所以可以互换，是因为题目没有说候选数组有序，但我们可以提前sort()。

排序之后，数组从i到末尾都是非递减的。一旦发现total + candidates[i] > target，那当前数字已经超了，排在它后面的数字只会更大或者相等，和自然也会更大，根本没有继续看下去的意义。所以可以直接break。

但如果你不排序，或者题目里出现了负数，那break就不能用了。负数的存在会让“后面的数越大”这个结论失效，甚至会让total + candidates[i] > target继续往下加负数又变小。这个陷阱我后面还会重点说，因为第 40 题同样会遇到。

2.4 直接 append 导致的深拷贝问题，是新手必踩的坑

我把这个坑放在本节最后，是因为它和思路无关，却会让结果看起来非常诡异。刷题初期我第一次写回溯时，结果是res.append(path)，最后输出的结果是[[], [], []]这类奇怪的形态，原因就是所有结果都引用同一个path列表。递归回退时不断pop()，之前已经“加入”结果的列表也被同步修改了，等到最后退出递归时，path已经空了，所有存下来的引用自然也都指向空列表。

正确写法是保存一个拷贝：

res.append(path[:])

path[:]会创建一个新的列表，后续path怎么增删都不会影响已经存好的结果。这个小细节看起来不起眼，但如果你直接拿动态语言写回溯，十有八九会碰到一次。

3. 40. 组合总和II：排序后的同级去重才是真正的门槛

3.1 不去重，同样一组组合会重复出现

第 40 题在第 39 题的基础上改了两个条件：候选数组里允许出现重复数字，而且每个数字在每个组合里只能使用一次。

如果不做任何特殊处理，直接套用刚才模板，问题就会变得很严重。举个例子，candidates = [1,1,2]，target = 3。排序后，两个 1 是两个不同的下标，但它们生成的组合却是一样的。

具体展开来看：

• 从第一个 1 开始，递归到下一层可以选第二个 1，也可以选 2；于是得到结果[1, 2]；
• 从第二个 1 开始，递归到下一层可以选 2；同样会得到[1, 2]。

这两个[1, 2]本质上是同一个组合，只是使用了数组中不同的 1 而已。如果不去重，结果集里就会出现重复项。

3.2 同一个 for 循环里的“同层去重”

去重的方案很直接：先把候选数组排序，让所有相等的数字相邻；然后在 for 循环里加一个条件，发现当前数字和上一个数字相同，并且此时不是递归深处、而是同一层枚举时，就跳过当前数字。

代码是这样写的：

if i > start and candidates[i] == candidates[i - 1]: continue

这里的i > start是整个去重逻辑的关键。它真正表达的意思是：我现在是在同一个 for 循环的同一层上，已经遍历过前一个相同值了。既然前一个相同值能生成的分支，后一个相同值也会原样生成一遍，那后一个分支就没有必要再走一次。

我用一个小例子验证这个逻辑。假设candidates = [1,1,2]，target = 3，去重后：

• i = 0，取第一个 1，递归；
• i = 1，因为i > 0且candidates[1] == candidates[0]，直接跳过；
• i = 2，取 2。

这样只会从第一个 1 出发，得到组合[1, 2]。请注意[1,1,2]里的两个 1 依然可以在同一个路径里同时出现，因为从第一个 1 递归进入下一层时，下一层的start = 1，在那个循环里i = 1，此时i == start，并不满足i > start，所以不会被跳过。这正好印证了上一节说的：同层不可重，但同枝可重。

3.3 只用candidates[i] == candidates[i-1]会出什么问题

有些题解会把去重条件简写成if candidates[i] == candidates[i-1]: continue，省略了i > start。这个写法表面上看也能过不少用例，但它有一个隐患：它分不清当前相等值到底是“同一层的重复”还是“递归深处的另一个元素”。

还是用[1,1,2]来举例。如果直接省略i > start，那么从第一个 1 递归到下一层时，start = 1，i = 1，candidates[1] == candidates[0]成立，于是第二个 1 也被跳过了。这会导致什么结果？会导致[1,1]这个合法路径彻底消失，你再也无法在组合中同时使用两个 1。

所以正确的省略方式应该是用used数组，而不是直接不加条件。

3.4 另一种常用做法：used 数组去重

在回溯专题里，used数组也是一种常见的去重方式，尤其在第 46 题全排列、第 47 题全排列II 里很常用。它的思路是：用一个布尔数组标记每个下标是否已被当前路径使用，然后在 for 循环里判断：

if i > 0 and candidates[i] == candidates[i-1] and not used[i-1]: continue

这个条件的意思更偏“引用关系”：如果前一个相同值没有被当前路径使用，说明当前是在同一层做重复枚举，应该跳过；如果前一个相同值已经被当前路径使用，说明是前后层的同一树枝，可以继续。

两种写法本质上等价，但i > start更轻量，不需要额外维护数组；used数组更通用，在其他回溯类型题目里迁移性好。我的建议是先把i > start练熟，因为从你现有代码改过去只需要加一行；等刷到排列类题目，再回头理解used也不迟。

3.5 和第 39 题的代码，只差两个细节

第 40 题完整代码在这里：

def combinationSum2(candidates, target): candidates.sort() res = [] def dfs(start, path, total): if total == target: res.append(path[:]) return if total > target: return for i in range(start, len(candidates)): if total + candidates[i] > target: break if i > start and candidates[i] == candidates[i - 1]: continue path.append(candidates[i]) dfs(i + 1, path, total + candidates[i]) path.pop() dfs(0, [], 0) return res

拿它和第 39 题对比，一眼就能看出只有两个变化：

• 递归调用从dfs(i, ...)变成了dfs(i + 1, ...)，因为每个数字只能用一次；
• for 循环里多了一行i > start and candidates[i] == candidates[i-1]，用来去重。

这个发现对构建信心很重要：LeetCode 中等题并不是从零造新东西，很多只是在一个基础模板上换约束条件。你能一眼认出模板，就能用最快速度完成改造。

4. 131. 分割回文串：把“切割”翻译成递归选择

4.1 切割问题如何映射到回溯框架

131 题和前面两道数组题看起来画风突变，它给的是一个字符串，比如s = "aab"，要求返回所有分割方案，使得每一段子串都是回文串。"aab"的可能方案有两个：["a","a","b"]和["aa","b"]。

为什么这个题也属于回溯？因为你本质上是在做组合选择：从字符串的第一个字符开始，选择一个回文前缀，把它切掉，再对剩余部分继续处理。这一层又一个选择，换一个前缀长度，就会产生新的分支，直到整个字符串被切完。

例如s = "aab"时的搜索过程：

• 从start = 0开始，可以选长度为 1 的前缀"a"，因为它回文；也可以选长度为 2 的"aa"，它也回文；但不能选长度为 3 的"aab"，因为它不回文；
• 如果选了"a"，就递归处理"ab"部分，前缀“a”可以切，之后"b"也能切；
• 如果选了"aa"，就递归处理"b"，剩下一个"b"直接切成单字符。

这就是一棵标准的回溯树。

4.2 递归结束条件与核心代码

这里递归函数的start不再表示数组下标，而是表示当前还没被切掉的字符串起始位置。当start == len(s)时，说明所有字符都已经切进path了，当前方案成立。

def partition(s): res = [] n = len(s) def dfs(start, path): if start == n: res.append(path[:]) return for end in range(start, n): sub = s[start:end + 1] if sub == sub[::-1]: # 判断回文 path.append(sub) dfs(end + 1, path) path.pop() dfs(0, []) return res

这段代码几乎就是我后来的“字符串切割”标准模板。循环枚举的是end，也就是当前切割片段的右边界；切片s[start:end+1]就是当前准备放入结果的一段子串；如果它是回文，就加入path，并从end + 1开始处理剩余部分；回溯时path.pop()把该片段拿走，换下一个右边界再试。

需要注意end + 1这个起点。它和组合总和里的i + 1逻辑完全一致：当前这一段已经用掉了，下一层只能从它的后一位开始，不能往回切，否则会重复。

4.3 回文判断的两种实现，我更推荐双指针

回文判断是实现这个题的一个小分支。第一种是利用 Python 切片的反转：

sub == sub[::-1]

写法很简洁，但每次切片段都会生成一个新字符串，对字符串很长的场景并不友好。第二种是双指针：

def is_pal(s, left, right): while left < right: if s[left] != s[right]: return False left += 1 right -= 1 return True

从刷题角度说，两种都能通过 131 题，因为题目给的字符串长度通常很小，复杂度不会成为瓶颈。但从面试表达角度，我更推荐双指针，因为它直观地体现了回文的定义：从两端向中间比较，一一对应。如果你在面试现场写出sub[::-1]，很容易继续解释“切片也可以”，但双指针几乎不需要额外解释。

4.4 这个题为什么不需要预计算回文矩阵

网上很多题解会先做一个二维布尔矩阵dp[i][j]，记录从 i 到 j 是否为回文，然后再用回溯。但我觉得第一次刷这个题时完全没必要上这个优化。

原因很简单：131 题里s.length最大通常只有十几或几十，回溯本身的分支数上限大约是2^(n-1)，每层再调一次 O(n) 的回文判断，整体也算量级可控。预计算回文矩阵属于“锦上添花”，而且很容易让你把注意力从回溯框架上移开。

如果你真的把三道题横向对比，会发现 131 题最值得掌握的其实是“切割点 = 选择分支”这个抽象能力。一个字符串的切割位置可以说是隐藏的“下标选择”，和组合问题里选一个数字本质上没有区别。

5. 三题代码骨架对比与实战中的三个坑

5.1 三段代码并排看，模板高度统一

把三道题的递归函数并排放在一起，你会发现它们长得非常像：

# 39. 组合总和 def dfs_39(start, path, 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_39(i, path, total + candidates[i]) # i，允许重复 path.pop() # 40. 组合总和II def dfs_40(start, path, total): if total == target: res.append(path[:]) return for i in range(start, len(candidates)): if total + candidates[i] > target: break if i > start and candidates[i] == candidates[i - 1]: continue # 同层去重 path.append(candidates[i]) dfs_40(i + 1, path, total + candidates[i]) # i+1，不重复 path.pop() # 131. 分割回文串 def dfs_131(start, path): if start == n: res.append(path[:]) return for end in range(start, n): if s[start:end + 1] == s[start:end + 1][::-1]: # 回文判断 path.append(s[start:end + 1]) dfs_131(end + 1, path) # end+1，切割跳过 path.pop()

三份代码的递归出口、for 循环、path 入栈出栈全是一模一样的结构。你可以用这个对比来检验自己是否真的看懂：如果面试官问“39 题为什么从 i 开始，40 题为什么从 i+1 开始”，你能不能一句话回答出来？

可以。39 题允许重复使用同一个数字，所以选完当前数字后，下一层依然可以选它；40 题每个数字只能用一次，所以下一层必须从后一位开始。这就是模板里的“起点变化”和题意约束的直接对应。

5.2 三题的关键参数对照表

从表中能直接看出一个规律：凡是候选数组有序的题目，剪枝都比较容易；凡是出现重复值的题目，去重的优先级要高于剪枝。因为去重影响的是正确性，剪枝影响的只是效率。如果去重写错了，结果会多出重复组合；如果剪枝写保守了，顶多慢一点。

5.3 坑一：结果全是空列表

这个坑我在第 39 题一节里已经说过，但它依然值得单独强调。只要你的res.append(path)没有加[:]，保存的永远是一个会被不断修改的引用。调试时如果发现打印出来的结果全是同一个空列表或者同一个最后状态，第一反应就应该检查这里。

5.4 坑二：把 39 的递归起点直接搬到 40

第 40 题最常见的错误是把 39 题的dfs(i, ...)原封不动保留，只加了个排序和去重。结果会怎么样？一个下标可以被再次选中，于是出现[2, 2, 3]这种看似合理的组合，但题面不允许同一个下标使用两次。你得同时检查两件事：起点是不是i+1，同层去重条件是不是i > start。这两行独立存在，缺一个都不行。

5.5 坑三：去重条件漏了i > start

反过来，有些人记住了要加去重条件，却写成了：

if candidates[i] == candidates[i - 1]: continue

少了i > start，会把“同枝”也误伤。比如[1,1,2]想得到[1,1,2]这个组合时，递归到第二层遇到第二个 1，因为candidates[1] == candidates[0]，直接被跳过，合法答案丢失。加入i > start之后，第二层i == start，不会触发跳过，问题才得到解决。

我刷题时用一组简单的测试数据验证：candidates = [1,1,2],target = 4。正确结果应该包含[1,1,2]。如果输出里看不到这个组合，那大概率就是去重条件过猛了。

5.6 刷完这三题后我还做的一件小事

这三道题全部跑通之后，我去翻了一下它们的兄弟题：77. 组合、216. 组合总和III。这两题和 39 题几乎是一模一样的套娃。77 题是从1..n里选 k 个数，对应模板就是起点从startIndex开始，递归出口变成len(path) == k；216 题是固定 k 个数凑 target，等于把出口条件改成len(path) == k and sum(path) == target。

如果你把 Day20 的三道题吃透，顺手再做这两道会非常轻松。这等于变相验证了一个结论：回溯专题刷到一定量之后，新题只是旧模板的约束条件改一改，真正需要你动脑的是识别清楚“选择是什么”和“递归完后怎么恢复现场”。

我个人的体会是，回溯题最耗时间的阶段反而不是写递归函数，而是写之前没把“决策模型”想清楚。只要能在心里把题面翻译成“每一层有哪些选择、选完以后起点怎么变、哪些情况必须去重”，代码通常十几分钟就能写完。建议你在刷完今天这三道题之后，也试着不用题解默写出这个模板，再用 77 题和 216 题做一次迁移练习，这会比盲目刷更多新题更有沉淀。