【笔面试算法学习专栏】回溯算法·进阶两题精讲（LeetCode 39. 组合总和、40. 组合总和 II）

摘要在掌握基础组合问题后本文深入讲解 LeetCode 39.组合总和与 40.组合总和 II 两道进阶题目。39题的关键突破在于递归参数从i1改为i实现元素可重复选取40题的核心难点是数组去重通过排序让相同元素相邻利用 used 数组实现树层去重策略。文章通过递归树图解、代码实现与复杂度分析系统对比两道题目的异同并提炼出四道组合题77/216/39/40的统一解题框架帮助读者彻底掌握回溯算法的核心技巧与面试高频考点。一、从基础到进阶问题演变的本质1.1 回顾基础题目在前一篇《回溯算法·基础两题精讲》中我们学习了 77.组合和 216.组合总和 III。这两道题的共同特点是数组元素互不相同如 [1,2,3,…,n]每个元素最多使用一次递归时传i11.2 进阶题目的新挑战本讲探讨两类变体题号题目数组特点元素使用规则39组合总和无重复元素可重复选取40组合总和 II有重复元素只能选一次问题演变的核心39题能不能重复选40题如果有重复怎么办这两个问题是回溯算法的核心难点也是面试中的高频考点。二、LeetCode 39. 组合总和元素可重复选取2.1 题目分析题目描述给定一个无重复元素的整数数组candidates和一个目标整数target找出candidates中所有可以使数字和为target的组合。关键约束同一个数字可以无限制重复被选取解集不能包含重复的组合示例输入: candidates [2,3,6,7], target 7 输出: [[2,2,3], [7]] 输入: candidates [2,3,5], target 8 输出: [[2,2,2,2], [2,3,3], [3,5]]2.2 与第77/216题的关键区别回顾之前的题目递归时总是传入i1# 77/216题每个数字只能使用一次self.backtrack(...,i1,...)这是因为之前的题目要求每个数字只能使用一次。而本题允许重复选取所以递归时应传入i而非i1# 39题可以重复选取当前数self.backtrack(...,i,...)# 传 i 而非 i12.3 核心变化解读为什么传i而不是i1当startIndex控制枚举起点时传i1下一轮从i1开始不能再选i不重复传i下一轮仍从i开始可以继续选i可重复candidates [2,3,6,7], target 7 传 i1 的搜索路径 2 → 3 → ... → 7 → 结束 选了2就不能再选2 传 i 的搜索路径 2 → 2 → 2 → ... → 3 → 3 → ... → 7 → 结束 选了2后还可以继续选22.4 递归树图解以candidates[2,3,6,7], target7为例[] 2 3 6 7 /|\ /|\ /|\ /| 2 3 6 7 2 3 6 7 2 3 6 7 2 3 6 7 /\ | /\ | /\ | | [2,2] ... [3,2] ... [6,?] ... ... ↓ ↓ [2,2,2] [2,3,2] ... 终止条件sum target - [2,2,3] → 2237 ✓ - [7] → 77 ✓重要观察由于我们仍然使用startIndex控制起点不同组合中数字的相对顺序是固定的例如[2,3] 和 [3,2] 只会出现一个不会产生重复组合这与数学中的组合定义一致2.5 剪枝优化剪枝条件sum candidates[i] target由于candidates中的数字都是正整数当sum candidates[i] target时后续更大的数字只会让和更大因此可以直接跳过优化策略对数组排序后可以利用有序性进行剪枝candidates.sort()# 先排序foriinrange(startIndex,len(candidates)):ifsumcandidates[i]target:break# 剪枝排序后后面的数更大直接跳过2.6 Python 代码实现classSolution:def__init__(self):self.result[]self.path[]defcombinationSum(self,candidates:List[int],target:int)-List[List[int]]:candidates.sort()# 排序便于剪枝self.backtrack(candidates,target,0,0)returnself.resultdefbacktrack(self,candidates:List[int],target:int,startIndex:int,current_sum:int):# 终止条件和等于target收集结果ifcurrent_sumtarget:self.result.append(self.path[:])return# 终止条件和超过target剪枝ifcurrent_sumtarget:return# 枚举所有可能的选择foriinrange(startIndex,len(candidates)):# 剪枝当前和 当前数 target 时后面的数更大直接跳过ifcurrent_sumcandidates[i]target:break# 做选择self.path.append(candidates[i])# 递归注意传 i 而不是 i1允许重复选取self.backtrack(candidates,target,i,current_sumcandidates[i])# 撤销选择self.path.pop()代码解析关键点说明candidates.sort()排序是剪枝的前提使相同元素相邻self.backtrack(..., i, ...)传i而不是i1这是本题与基础题的核心区别break在循环中排序后一旦超过目标后面的数更大直接跳出循环2.7 复杂度分析时间复杂度O(S)O(S)O(S)其中SSS是所有可行解的长度之和。实际较难精确计算因为搜索树的大小取决于具体输入。空间复杂度O(targetmin(candidates))O(\frac{target}{min(candidates)})O(min(candidates)target​)递归栈的最大深度取决于能选入多少个最小数字。2.8 运行结果验证solutionSolution()print(solution.combinationSum([2,3,6,7],7))# 输出: [[2,2,3], [7]]print(solution.combinationSum([2,3,5],8))# 输出: [[2,2,2,2], [2,3,3], [3,5]]三、LeetCode 40. 组合总和 II数组去重的艺术3.1 题目分析题目描述给定一个可能含有重复元素的整数数组candidates和一个目标整数target找出candidates中所有可以使数字和为target的组合。关键约束每个数字在每个组合中只能使用一次解集不能包含重复的组合示例输入: candidates [10,1,2,7,6,1,5], target 8 输出: [[1,1,6], [1,2,5], [7]] 输入: candidates [2,5,2,1,2], target 5 输出: [[1,2], [5]]观察第一个例子中有两个1但结果中 [[1,1,6]] 只有一个第二个例子中有两个2但结果中 [[1,2]] 只有一个3.2 本题的特殊挑战本题的难点在于“去重”数组有重复元素如 [1,1,2,5,…]其中有两个1结果不能有重复组合不能出现 [[1a,6], [1b,6]] 这样的重复3.3 去重的核心思想树层去重 vs 树枝去重理解这个概念是解决本题的关键candidates [1,1,2,5], target 5 树层同一层相同值只选第一个 - 选第一个1继续搜索 → [1,2], [1,5] ... - 选第二个1跳过因为第一个1已经探索过这个分支的效果 树枝同一路径可以选相同的值 - 选第一个1后可以再选第二个1 → [1,1,3] ...为什么树层要跳过相同值因为选第一个11 → [1,2] ✓选第二个11 → [1,2] ✗重复两者的搜索结果是相同的都得到 [1,2]但选第二个1会做重复的搜索所以要跳过。3.4 如何判断同层相同值策略排序 used 数组排序让相同元素相邻used 数组标记元素是否被当前路径选用判断条件ifi0andcandidates[i]candidates[i-1]andused[i-1]False:continue# 跳过同层重复used[i-1] 的含义used[i-1] True同一树枝前一个元素被选过当前路径上选过used[i-1] False同一树层前一个元素没有被选不在当前路径上同一树枝usedTrue可以选 path [1(第一个1)] → used[0]True → 可以选 candidates[1]1used[1-1]used[0]True 同一树层usedFalse跳过 path [] → 遇到 candidates[1]1 时used[0]False同层的前一个1没被选跳过3.5 递归树图解以candidates[1,1,2,5], target5为例[] 1(used[0]T) 2 5 / \ / | /| 1(used[1]T) 2 1(used[?]) 5 ... / \ | | | 1 2 ... ... ... | | [1,1,?] [1,2,?] ↓ ↓ [1,1,3] [1,2,2] ✓ 树层去重详解 - 根节点选第一个1后递归进入左子树 - 根节点若要选第二个1used[0]False会被跳过 最终结果[[1,1,3], [1,2,2], [2,3], [5]] ↑ 去重后只有一个 [1,1,3]3.6 Python 代码实现classSolution:def__init__(self):self.result[]self.path[]defcombinationSum2(self,candidates:List[int],target:int)-List[List[int]]:candidates.sort()# 关键1排序使相同元素相邻self.backtrack(candidates,target,0,0,[False]*len(candidates))returnself.resultdefbacktrack(self,candidates:List[int],target:int,startIndex:int,current_sum:int,used:List[bool]):ifcurrent_sumtarget:self.result.append(self.path[:])returnifcurrent_sumtarget:returnforiinrange(startIndex,len(candidates)):# 剪枝排序后超过目标直接跳过ifcurrent_sumcandidates[i]target:break# 关键2树层去重# 同层相同元素前一个没被选过则跳过ifi0andcandidates[i]candidates[i-1]andnotused[i-1]:continue# 做选择self.path.append(candidates[i])used[i]True# 递归传 i1每个元素只用一次self.backtrack(candidates,target,i1,current_sumcandidates[i],used)# 撤销选择self.path.pop()used[i]False代码解析关键点说明candidates.sort()排序是去重的前提used数组标记元素是否在当前路径上i 0 and candidates[i] candidates[i-1] and not used[i-1]核心去重条件self.backtrack(..., i 1, ...)传i1每个元素只用一次3.7 去重条件详解为什么要i 0因为比较candidates[i]和candidates[i-1]i0时没有i-1。为什么要 candidates[i] candidates[i-1]只有相同元素才需要去重。为什么要 not used[i-1]used[i-1] True同一树枝前一个元素在当前路径上被选过可以选used[i-1] False同一树层前一个元素没被选过同级跳过图示 [] / \ [1]a [1]b ← 同层两个1 / \ [1]a [1]b ← used[a]True可以选 | | [...] [...] ← 搜索结果相同需要去重 当遍历到 [1]b 时 - candidates[b] candidates[a] ✓ - used[a] True → not used[a] False - 条件不满足b 不会被跳过 不对让我重新分析 在根节点遍历时 - i0选第一个1used[0]True - i1candidates[1]candidates[0] 且 used[0]True → not used[0]False → 不跳过 等等这样第一个1和第二个1都会被选 我理解错了让我重新画递归树 递归树 [] 1(used[0]T) 2 5 / | / 1(used[1]T) 2 5 / \ | | 1 2 ... ... 第一层循环i从0开始 - i0: candidates[0]1, used[0]False - i1: candidates[1]1 candidates[0], used[0]True → not used[0]False → 不跳过 这是错的让我重新理解... 实际上第一次选第一个1时 - path.append(1), used[0]True - backtrack递归进入下一层 - 下一层循环时used[0]仍然是True - 所以第二层的i0第一个1会被跳过因为used[0]True表示在当前路径上 回溯后used[0]False回到第一层 第一层继续i1 - candidates[1]1 candidates[0], used[0]False → 跳过 所以同层的前一个相同元素没被选过才跳过。3.8 复杂度分析时间复杂度O(2n)O(2^n)O(2n)最坏情况下需要遍历所有可能的子集。空间复杂度O(n)O(n)O(n)递归栈深度最多为nnn数组长度。四、两道进阶题的深度对比4.1 核心区别表维度39. 组合总和40. 组合总和 II数组特点无重复元素有重复元素元素使用可重复选取只能选一次递归参数i可重复i1不重复去重需求不需要需要树层去重关键步骤剪枝优化排序 used数组4.2 去重方法总结39题不需要去重数组无重复通过startIndex控制的顺序已经保证了组合唯一传i而不是i140题需要去重排序让相同元素相邻used数组标记元素是否被当前路径选用跳过条件i 0 and candidates[i] candidates[i-1] and not used[i-1]4.3 去重的记忆口诀“同层相同跳过树枝相同可选”五、四道组合题的统一框架将四道组合题77/216/39/40统一考虑┌─────────────────────────────────────────────────────────┐ │ 回溯解题框架 │ ├─────────────────────────────────────────────────────────┤ │ │ │ 1. 终止条件 │ │ - 数量约束: len(path) k │ │ - 和约束: current_sum target │ │ │ │ 2. 递归遍历 │ │ - 基础组合(77/216): 传 i1 │ │ - 元素可重复(39): 传 i │ │ - 数组有重复(40): 传 i1 树层去重 │ │ │ │ 3. 剪枝策略 │ │ - 数量剪枝: i n - (k - len(path)) 1 │ │ - 和剪枝: current_sum candidates[i] target │ │ │ │ 4. 去重策略仅40题 │ │ - 排序 used数组 条件跳过 │ │ │ └─────────────────────────────────────────────────────────┘5.1 判断使用哪种策略拿到组合类问题先问自己三个问题问题1数组有重复元素吗有 → 需要考虑去重排序 used无 → 直接用 startIndex 控制问题2元素可以重复选取吗可以 → 递归传i不可以 → 递归传i1问题3有数量约束吗有 → 终止条件加len(path) k无 → 只用和约束5.2 策略组合表题号数组重复元素可重复数量约束递归参数去重77无否是i1无216无否是i1无39无是否i无40有否否i1树层去重六、常见错误与避坑指南6.1 忘记排序错误40题不排序就去重# 错误不排序相同元素不相邻无法去重candidates[1,2,1,3]self.backtrack(candidates,...)# 正确先排序candidates.sort()# [1, 1, 2, 3]self.backtrack(candidates,...)6.2 used 条件写反错误树枝和树层混淆# 错误used[i-1] True 是树枝False 是树层ifused[i-1]True:# 这是树枝去重错了continue# 正确同层且前一个相同元素没被选过才跳过ifnotused[i-1]:# 同层前一个没被选过跳过continue6.3 忘记重置 used错误回溯时忘记恢复 used 状态# 错误没有 used[i] Falseself.path.pop()# 正确撤销选择self.path.pop()used[i]False6.4 引用复制错误错误添加到结果时直接 append path# 错误引用复制self.result.append(self.path)# 正确值复制self.result.append(self.path[:])七、扩展与延伸7.1 回溯问题的本质回溯问题的本质是在解空间树上的搜索。解空间树的大小决定了算法的时间复杂度。优化方向剪枝提前排除不可能产生解的分支去重避免搜索重复的解空间排序剪枝利用有序性进行更激进的剪枝7.2 相关题目推荐题号题目难度推荐理由47全排列 II中等含重复的全排列需要去重78子集中等子集问题的回溯解法90子集 II中等含重复的子集需要去重51N皇后困难经典回溯综合应用7.3 面试高频考点回溯算法在面试中经常考察核心要点能画递归树清晰展示搜索过程能解释去重说明树层去重和树枝去重的区别能推导剪枝解释剪枝条件的数学原理能写出代码完整代码无语法错误八、总结本文通过两道进阶题目深入讲解了回溯算法的两个高级主题核心知识点元素可重复选取只需将递归参数从i1改为i数组去重通过排序 used数组实现树层去重关键公式去重条件i 0 and candidates[i] candidates[i-1] and not used[i-1]记忆口诀“同层相同跳过树枝相同可选”面试要点能区分树层去重和树枝去重能正确写出 used 数组的判断条件能解释为什么排序是去重的前提掌握这些技巧后回溯类问题将不再困难。无论是面试还是竞赛都能游刃有余。