LeetCode 39组合总和与131分割回文串的深度解析

1. 项目概述

今天要分享的是代码随想录算法训练营第23天的两道经典题目：LeetCode 39组合总和和LeetCode 131分割回文串。这两道题在面试中出现的频率相当高，特别是组合总和，几乎是大厂必考的题目类型。我自己在准备面试时，这两道题都反复刷了不下十遍，每次都有新的收获。

组合总和考察的是回溯算法的经典应用，而分割回文串则是回溯与动态规划的结合。很多同学刚开始接触这类题目时，常常会被各种边界条件绕晕，或者写出时间复杂度爆炸的解法。今天我就结合自己的刷题经验，带大家彻底吃透这两道题。

2. LeetCode 39 组合总和详解

2.1 题目理解与思路分析

题目给定一个无重复元素的整数数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的数字可以无限制重复选取。

示例： 输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]]

这道题的核心在于：

1. 同一个数字可以重复使用
2. 解集不能包含重复的组合
3. 所有数字都是正整数

关键点：为了避免重复解，我们需要控制搜索的起始位置，并且对数组进行排序。

2.2 回溯算法实现

def combinationSum(candidates, target): res = [] candidates.sort() # 先排序方便剪枝 def backtrack(start, path, remaining): if remaining == 0: res.append(path.copy()) return for i in range(start, len(candidates)): if candidates[i] > remaining: break # 剪枝 path.append(candidates[i]) backtrack(i, path, remaining - candidates[i]) # 注意这里传i而不是i+1 path.pop() backtrack(0, [], target) return res

2.3 关键点解析

1. 排序剪枝：先对数组排序，当当前数字大于剩余target时可以直接break，避免不必要的递归。

2. 传递start参数：这是避免重复组合的关键。每次递归都从当前索引开始，而不是从头开始。

3. 递归终止条件：当remaining减到0时，说明找到了一个有效组合。

2.4 时间复杂度分析

最坏情况下时间复杂度是O(N^(target/min))，其中min是数组中最小的数。空间复杂度是O(target/min)，主要是递归栈的深度。

3. LeetCode 131 分割回文串详解

3.1 题目理解与思路分析

题目要求将字符串s分割成若干子串，使得每个子串都是回文串。返回所有可能的分割方案。

示例： 输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]

这道题有两个关键点：

1. 如何高效判断子串是否是回文
2. 如何生成所有可能的分割方案

3.2 动态规划预处理

为了提高效率，我们可以先用动态规划预处理回文信息：

def partition(s): n = len(s) dp = [[False]*n for _ in range(n)] for i in range(n-1, -1, -1): for j in range(i, n): if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]): dp[i][j] = True

这个DP表表示s[i..j]是否是回文。

3.3 回溯算法实现

def partition(s): res = [] n = len(s) # 预处理DP表 dp = [[False]*n for _ in range(n)] for i in range(n-1, -1, -1): for j in range(i, n): if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]): dp[i][j] = True def backtrack(start, path): if start == n: res.append(path.copy()) return for end in range(start, n): if dp[start][end]: path.append(s[start:end+1]) backtrack(end+1, path) path.pop() backtrack(0, []) return res

3.4 关键点解析

1. DP预处理：避免了每次判断回文都要O(n)的时间，将回文判断优化到O(1)。

2. 回溯过程：每次找到一个回文子串就加入路径，然后递归处理剩余部分。

3. 终止条件：当start指针走到字符串末尾时，说明找到了一个完整的分割方案。

4. 常见问题与优化技巧

4.1 组合总和的常见错误

1. 忘记排序：不排序就无法进行有效的剪枝，导致性能下降。

2. 重复组合：如果不控制start参数，会产生如[2,2,3]和[2,3,2]这样的重复解。

3. 终止条件错误：有些同学会写成if sum(path) == target，这样每次都要计算sum，效率很低。

4.2 分割回文串的优化

1. 记忆化搜索：除了DP预处理，也可以用记忆化搜索来缓存已经判断过的回文子串。

2. 提前终止：当剩余字符串长度小于当前回文长度时，可以提前终止搜索。

3. 双指针判断：如果不想用DP，也可以用双指针法判断回文，但时间复杂度会更高。

4.3 调试技巧

1. 打印递归树：在递归函数开头打印当前状态，可以直观看到搜索过程。

2. 小数据测试：先用小的测试用例手动模拟，确保理解正确。

3. 边界检查：特别注意空输入、单个元素等边界情况。

5. 相似题目推荐

1. 组合总和II（LeetCode 40）：数字不能重复使用，但数组可能有重复元素。

2. 分割回文串II（LeetCode 132）：求最少分割次数，适合用动态规划解决。

3. 子集（LeetCode 78）：回溯的经典入门题。

4. 全排列（LeetCode 46）：理解回溯中used数组的使用。

6. 个人刷题心得

刷这两道题时，我最大的体会是一定要动手画递归树。刚开始可能会觉得麻烦，但画几次后就会对回溯的过程有更直观的理解。特别是对于组合总和，画出递归树能清楚地看到为什么要传start参数。

另一个心得是不要过早优化。我一开始做分割回文串时，总想着一步到位写出最优解，结果反而被各种边界条件搞晕。后来先写出暴力解法，再逐步优化，思路就清晰多了。

最后分享一个小技巧：在IDE里调试回溯算法时，可以在递归调用前后打印当前状态，这样能更清楚地看到程序是如何回溯的。比如：

print(f"进入递归：start={start}, path={path}, remaining={remaining}") backtrack(start, path, remaining) print(f"退出递归：start={start}, path={path}, remaining={remaining}")