教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇基于「算法通关手册」AlgoNote题库解析完整拆解 LeetCode 0040「组合总和 II」的题目约束、回溯算法设计与同层去重技巧。读完你将掌握如何用排序 回溯解决每个元素只能使用一次、解集不重复的组合枚举问题并理解它与「组合总和」「子集 II」「全排列 II」等经典回溯题之间的去重差异。题目基本信息题号与名称0040. 组合总和 IICombination Sum II标签数组、回溯难度中等仓库位置完整题解见 combination-sum-ii.md题目索引见 0001-0099 题解列表题目大意给定一个数组candidates和一个目标数target要求找出candidates中所有可以使数字和为目标数target的组合。说明与约束数组candidates中的数字在每个组合中只能使用一次注意这是与「组合总和」最大的区别后者允许无限次选取。$1 \le candidates.length \le 100$。$1 \le candidates[i] \le 50$。解集不能包含重复的组合。示例示例 1输入: candidates [10,1,2,7,6,1,5], target 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]观察该示例输入中出现了两个1因此[1,1,6]是合法解两个1来自两个不同下标但[1,7]只出现一次——不能因为有两个1就输出两个相同的[1,7]。这正是本题去重的核心。示例 2输入: candidates [2,5,2,1,2], target 5, 输出: [ [1,2,2], [5] ]解题思路回溯算法本题是典型的「组合类」回溯问题。它与「0039. 组合总和」的不同点在于本题的candidates可能包含重复元素且每个元素在每个组合中只能使用一次最终解集不能包含重复组合。因此关键步骤在于去重。在「算法通关手册」的回溯算法教程中给出了回溯算法的通用框架明确所有选择 → 明确终止条件 → 将决策树与终止条件翻译成代码其核心循环是做选择 → 递归搜索 → 撤销选择。本题的代码实现正是这一模板的典型应用。两个去重关键点纵向去重每层向下下一层递归的start_index要从当前节点的后一位开始遍历即从i 1位开始。这样保证每个元素在当前组合中最多被使用一次避免在同一路径上重复取同一个下标对应的元素。横向去重同一层内同一递归层不能使用值相同的元素即需要增加一句判断if i start_index and candidates[i] candidates[i - 1]: continue这里的i start_index很关键它只跳过同一层内重复值的后续分支而不会跳过不同层中相同值的合法使用例如示例 1 中的[1,1,6]两个1位于不同层依然合法。前提条件先排序为了让相邻相同元素可以被检测必须先对candidates排序。排序后所有值相同的元素相邻排列去重判断candidates[i] candidates[i - 1]才能正确工作。决策树视角把回溯过程画成决策树每一层代表组合中的一个位置每个节点代表当前已选元素列表。由于start_index从i 1开始搜索树是收敛的每深入一层可选范围缩小由于同层去重值相同的兄弟分支只保留第一个从而保证解集不重复。思路 1完整代码以下是本题题解中的 Python 实现完整代码见 combination-sum-ii.mdclass Solution: res [] path [] def backtrack(self, candidates: List[int], target: int, sum: int, start_index: int): if sum target: return if sum target: self.res.append(self.path[:]) return for i in range(start_index, len(candidates)): if sum candidates[i] target: break if i start_index and candidates[i] candidates[i - 1]: continue sum candidates[i] self.path.append(candidates[i]) self.backtrack(candidates, target, sum, i 1) sum - candidates[i] self.path.pop() def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]: self.res.clear() self.path.clear() candidates.sort() self.backtrack(candidates, target, 0, 0) return self.res代码逐段拆解全局变量设计res存放所有符合条件的组合path存放当前递归路径下的组合。res、path声明为类属性因此入口函数开头必须self.res.clear()、self.path.clear()防止多次调用之间残留上次结果。终止条件sum target当前和已超过目标直接返回剪枝sum target找到一个合法组合将path[:]拷贝后加入res必须拷贝避免后续path修改污染已保存结果。循环内的两道防线if sum candidates[i] target: break由于数组已升序排序当前元素已使和超目标后面更大的元素必然也超目标可以直接break跳出循环这是有序数组带来的高效剪枝if i start_index and candidates[i] candidates[i - 1]: continue同层去重跳过重复值分支。选择与撤销sum candidates[i]、path.append(candidates[i])做选择递归调用backtrack(..., i 1)注意是i 1而非i保证元素只用一次递归返回后sum - candidates[i]、path.pop()撤销选择恢复现场。该解法同样适用于剑指 Offer 系列的同源题目「LCR 082. 组合总和 II」其约束1 ≤ candidates[i] ≤ 50、元素只能用一次、组合不重复与本题完全一致代码实现几乎相同。思路 1复杂度分析时间复杂度$O(2^n \times n)$其中 $n$ 是数组candidates的元素个数$2^n$ 指的是所有状态数。每个状态需要 $O(n)$ 的时间构造组合将path拷贝进res。空间复杂度$O(target)$。递归函数需要栈空间栈空间取决于递归深度最坏情况下递归深度为 $O(target)$例如candidates全为1且target很大时所以空间复杂度为 $O(target)$。需要说明的是虽然剪枝与去重能显著减少实际搜索量但从渐进复杂度的上界看仍为指数级这也是回溯类问题在解空间较大时的固有特点。与同系列回溯题的横向对比「算法通关手册」中还有多道与本题共享同一套排序 去重思想的题目理解它们的差异可以一次性吃透回溯去重题目元素可重复使用元素是否可能重复去重手段参考题解0039. 组合总和是i否元素互不相同无需同层去重combination-sum.md0040. 组合总和 II否i 1是排序 i start_index同层跳过combination-sum-ii.md0216. 组合总和 III否i 1否1~9 各一次无需同层去重需数量约束combination-sum-iii.md0047. 全排列 II否用visited标记是排序 not visited[i-1]判重permutations-ii.md0090. 子集 II否i 1是排序 i index同层跳过subsets-ii.md要点归纳能否重复选取决定递归参数可重复选取传i如 0039 组合总和不可重复传i 1本题。数组是否存在重复元素决定是否需要同层去重存在重复元素时先排序再用当前元素与前一个元素相等且不是本层第一个的条件continue跳过本题与 0090 子集 II 一致。全排列类问题0047 全排列 II因为每个位置都能选所有元素需要额外的visited数组标记使用状态其判重条件为if i 0 and nums[i] nums[i - 1] and not visited[i - 1]: continue语义是同一层跳过与上一个相同、且上一个尚未被使用的分支。总结「组合总和 II」是回溯算法中组合 去重的标杆题目。解题的核心链条是排序为去重与剪枝创造前提start_index i 1保证每个元素在一个组合中只用一次同层去重if i start_index and candidates[i] candidates[i - 1]: continue保证解集不重复有序剪枝if sum candidates[i] target: break提前终止不可能的分支。掌握了这套排序 回溯 同层去重的组合拳即可举一反三解决子集 II、全排列 II 等所有含重复元素的枚举类问题。更多回溯练习题目可在 00_06 分类题目列表回溯算法题目 中按需检索。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐GitHub_Trending/leetcode1/leetcode组合总和II回溯法的排序与去重GitHub_Trending/leetcode1/leetcode组合总和II回溯法的排序与去重 问题引入与核心挑战 在LeetCode算法题库中组合总和示例工程教程LeetCode 40. 组合总和 II 题解基于回溯法通用框架的排序去重实战JS / Python3 / CLeetCode 40. 组合总和 II 题解基于回溯法通用框架的排序去重实战JS / Python3 / C 本篇文章围绕 LeetCode 40「文档教程知识库LeetCode 40 Combination Sum II组合总和 II全解法剖析排序去重回溯、频次映射与剪枝优化LeetCode 40 Combination Sum II组合总和 II全解法剖析排序去重回溯、频次映射与剪枝优化 导读 本文以仓库 articles/示例工程教程上一篇终极免费方案解锁小爱音箱音乐会员限制畅享无限播放下一篇告别直播杂音OBS-VST插件让你轻松获得专业级音频效果创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考