★ FEATURED ARTICLE 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]]这道题的核心在于同一个数字可以重复使用解集不能包含重复的组合所有数字都是正整数关键点为了避免重复解我们需要控制搜索的起始位置并且对数组进行排序。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而不是i1 path.pop() backtrack(0, [], target) return res2.3 关键点解析排序剪枝先对数组排序当当前数字大于剩余target时可以直接break避免不必要的递归。传递start参数这是避免重复组合的关键。每次递归都从当前索引开始而不是从头开始。递归终止条件当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]]这道题有两个关键点如何高效判断子串是否是回文如何生成所有可能的分割方案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[i1][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[i1][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:end1]) backtrack(end1, path) path.pop() backtrack(0, []) return res3.4 关键点解析DP预处理避免了每次判断回文都要O(n)的时间将回文判断优化到O(1)。回溯过程每次找到一个回文子串就加入路径然后递归处理剩余部分。终止条件当start指针走到字符串末尾时说明找到了一个完整的分割方案。4. 常见问题与优化技巧4.1 组合总和的常见错误忘记排序不排序就无法进行有效的剪枝导致性能下降。重复组合如果不控制start参数会产生如[2,2,3]和[2,3,2]这样的重复解。终止条件错误有些同学会写成if sum(path) target这样每次都要计算sum效率很低。4.2 分割回文串的优化记忆化搜索除了DP预处理也可以用记忆化搜索来缓存已经判断过的回文子串。提前终止当剩余字符串长度小于当前回文长度时可以提前终止搜索。双指针判断如果不想用DP也可以用双指针法判断回文但时间复杂度会更高。4.3 调试技巧打印递归树在递归函数开头打印当前状态可以直观看到搜索过程。小数据测试先用小的测试用例手动模拟确保理解正确。边界检查特别注意空输入、单个元素等边界情况。5. 相似题目推荐组合总和IILeetCode 40数字不能重复使用但数组可能有重复元素。分割回文串IILeetCode 132求最少分割次数适合用动态规划解决。子集LeetCode 78回溯的经典入门题。全排列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})
阅读完成 · 觉得有帮助？
