文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载本文基于 InterviewGuide 仓库中阿秀的刷题笔记原题解析文档展开完整讲解力扣 40 题组合总和 II的经典回溯解法为什么必须先排序、i begin candidates[i] candidates[i-1]这一行去重代码的真正含义、以及每个数字只能使用一次与 39 题模板的差异。读完本文你将掌握组合类回溯题的核心套路——树层去重并能直接迁移到子集 II、全排列 II 等同类题目。一、题目回顾带重复元素的凑 target问题给定一个数组candidates和一个目标数target找出candidates中所有可以使数字和为target的组合。与 39 题最大的不同点有两个candidates可能包含重复数字candidates中的每个数字在每个组合中只能使用一次注意是每个组合内只能用一次而数组中若有两个相同的数字则它们可以在同一个组合中各自出现一次。题目说明所有数字包括目标数target都是正整数解集不能包含重复的组合。示例 1输入: candidates [10,1,2,7,6,1,5], target 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]示例 2输入: candidates [2,5,2,1,2], target 5, 所求解集为: [ [1,2,2], [5] ]注意示例 1 中出现了[1, 1, 6]数组里有两个 1它们可以同时被选进一个组合但组合[1, 7]不能因为数组里有两个 1 而出现两次。这正是本题去重的核心矛盾。二、核心难点重复元素下如何不产生重复组合如果你直接套用39. 组合总和的经典回溯模板会得到一个错误的结果[1, 7]会以两种不同路径被重复收集第一次用下标 0 的 1第二次用下标 3 的 1但它们对应的组合是同一个。要理解去重必须先区分回溯过程中重复产生的两个层面同一层重复树层去重在同一轮for循环中如果两个位置的值相同选择它们会得到相同分支的相同组合。例如在candidates [1,1,2,5,6,7,10]的第一层选择中下标 0 的 1 和下标 1 的 1 作为组合的第一个数字是等价的必须只取一个。不同层重复树枝重复[1, 1, 6]中两个 1 分别出现在组合的不同深度先选下标 0 的 1再在下一层选下标 1 的 1这是合法的因为数字在组合中只能使用一次不等于数值相同的元素不能同时出现。因此去重的正确姿势是先对candidates排序让相同元素相邻然后在每一层for循环中跳过与前一个元素值相同的位置。排序是这一切的前提——这也是原笔记反复强调关键在于去重的原因。三、C 解法排序 同层跳过去重原笔记代码原文档给出的完整解法如下提交记录执行用时 0 ms击败 100.00% 的 C 提交内存消耗 7.1 MB击败 100.00% 的提交数据记录于原笔记void combinationSum2Core(vectorint candidates, vectorvectorint result, vectorint temp, int target, int begin, int sum) { if (sum target) { result.push_back(temp); return; } for (int i begin; i candidates.size(); i) { if (i begin candidates[i] candidates[i - 1]) continue; // 同层去重 if (sum candidates[i] target) { temp.push_back(candidates[i]); combinationSum2Core(candidates, result, temp, target, i 1, sum candidates[i]); temp.pop_back(); // 回溯 } else return; // 剪枝 } } vectorvectorint combinationSum2(vectorint candidates, int target) { sort(candidates.begin(), candidates.end()); // 去重前提 剪枝前提 vectorint temp; vectorvectorint result; combinationSum2Core(candidates, result, temp, target, 0, 0); return result; }递归函数的参数含义如下参数含义candidates候选数组调用前已升序排序result最终解集sum target时收集temptemp当前正在构造的组合决策路径target目标值与sum比较决定是否收集与剪枝begin本轮选择列表的起点下标保证组合而不是排列不回头选前面的元素sum当前temp中元素的和3.1 逐行拆解关键逻辑① 去重那一行if (i begin candidates[i] candidates[i - 1]) continue;i begin保证只对当前层非第一个位置做判断。i begin是该层选择列表的第一个元素没有前驱可比较同时也避免误伤上一层已经选过相同值、但当前层第一次出现该值的合法情况。candidates[i] candidates[i - 1]排序后相同值相邻若当前元素与同层前一个元素值相等说明以这个值作为本层选择的组合已经在前一次迭代中被完整搜过一遍直接continue跳过避免产生重复组合。这正好实现了上一节说的树层去重、树枝放行同一个值在本层只做一次决策但可以在下一层递归里begin前移再次被选取从而保留[1, 1, 6]这类合法结果。② 剪枝那一行if (sum candidates[i] target)...else return;因为candidates已升序排序一旦某个candidates[i]加上当前和超过target后面的元素只会更大更不可能凑出目标。此时不必继续遍历直接return终止整个for循环排序保证了后续元素全部超限。这是与排序相辅相成的剪枝优化。③i 1与 39 题i的区别递归调用传的是i 1意味着当前下标及之前的元素不会再被选取天然保证了每个数字在每个组合中只能使用一次。对比39. 组合总和中递归传的是i表示同一个数字可以无限次重复选取。是否可重复选取只差在递归参数传i还是i 1这是组合类回溯的一行之差。④ 回溯temp.pop_back();递归返回后弹出当前元素撤销本次选择恢复现场让for循环继续尝试下一个候选值。这是回溯算法决策 → 递归 → 撤销决策三段式结构的标配。四、去重的两种等价实现相邻比较法与哈希表法仓库中其他重复元素 去重的题目给出了不同实现思路可以做横向对照4.1 相邻比较法本题采用if (i begin candidates[i] candidates[i - 1]) continue;依赖排序零额外空间是组合类题目最推荐的写法。4.2 哈希表法仓库 90. 子集 II 采用在90. 子集 II中原笔记给出了两种实现其中一种是在每层for循环内维护一个unordered_map记录本层已经选过的值void subsetsWithDupCore(vectorint nums, vectorvectorint result, vectorint temp, int index) { result.push_back(temp); // 子集全部路径都要收集 unordered_mapint, int mp; for (int i index; i nums.size(); i) { if (mp[nums[i]] 0) continue; // 本层已选过该值跳过 temp.push_back(nums[i]); subsetsWithDupCore(nums, result, temp, i 1); temp.pop_back(); mp[nums[i]]; } }同样地47. 全排列 II的回溯 剪枝解法也用unordered_mapint, int mp在每一层标记同层次此元素已使用多次再次使用必造成重复全排列直接跳过。可见**层内去重有两种工具排序 相邻比较或者哈希表记录**。前者省空间后者不依赖排序但本题的剪枝仍依赖排序所以相邻比较法更贴合本场景。另一种常见的等价写法是用used[]布尔数组记录元素是否被使用过配合used[i-1] false判断同层重复其去重效果与相邻比较法一致读者可以根据习惯选择。五、算法过程模拟为什么[1, 1, 6]能被保留以示例 1 排序后的candidates [1, 1, 2, 5, 6, 7, 10]、target 8为例手动推演去重逻辑第一层begin 0sum 0i 0选1i begin不去重进入递归i 1时candidates[1] candidates[0] 1且i begin跳过避免了第二个 1 作为组合首元素重复展开i 2选2……以此类推。第二层从选1的分支进入begin 1sum 1此时i 1 begincandidates[1] 1不会被跳过于是可以再选一个 1得到temp [1, 1]。这正是[1, 1, 6]的来源——同值元素出现在不同深度时被放行。剪枝当sum candidates[i] 8时如i指向10直接return不再展开。可以看到去重判断是分层生效的begin的每次变化重置了本层是否已选过该值的上下文这与哈希表法每层新建mp的原理完全一致。六、与 39. 组合总和的完整对照对比维度39. 组合总和40. 组合总和 II本文候选数组无重复元素可能包含重复元素每个数字使用次数无限制重复选取每个组合中最多一次是否必须先排序排序便于剪枝必须排序去重的前提递归参数传i可重复取同一元素传i 1取过即不可再取去重逻辑无需i begin candidates[i] candidates[i - 1]跳过剪枝逻辑sum candidates[i] target否则return相同都依赖升序39 题的经典模板仓库原笔记代码如下读者可逐行对比void combinationSumCore(vectorvectorint res, vectorint candidates, int target, vectorint tmp, int sum, int begin) { if (sum target) { res.push_back(tmp); } else { for (int i begin; i candidates.size(); i) { if (sum candidates[i] target) { tmp.push_back(candidates[i]); combinationSumCore(res, candidates, target, tmp, sum candidates[i], i); // 注意传 i tmp.pop_back(); } else { return; } } } }两题的差别浓缩为两处递归传i还是i 1决定能否重复选以及是否多一行同层去重判断决定重复元素是否产生重复组合。七、复杂度分析与边界情况时间复杂度最坏情况下需要枚举候选数组中每个元素取 / 不取的全部子集回溯节点数约为O(2^n)n为候选数组长度将每个合法组合复制进结果还会产生额外开销整体可视为O(n * 2^n)量级。同层去重与sum剪枝能显著压缩实际搜索空间。空间复杂度递归深度不超过ntemp长度同样不超过n额外空间为O(n)不计存储结果所需的空间。边界情况若candidates中没有元素能凑出targetresult为空逻辑天然正确若candidates中某元素本身就等于target它会在第一层被选入并作为单元素组合收集空数组 / 空target等极端输入不会越界for循环天然处理。八、拓展组合 / 子集 / 全排列三类回溯的去重同构去重思想在回溯算法章节中是成体系的仓库精选力扣 300 道算法题的回溯部分完整收录了这条知识链39. 组合总和无重复 可重复选取经典模板起点40. 组合总和 II本文有重复 限选一次排序 同层去重78. 子集 与 90. 子集 II子集收集全部路径90 题同样依赖排序 层内去重46. 全排列 与 47. 全排列 II排列允许回头用swap交换 哈希表层内剪枝。可以总结出一条实战口诀组合问题用begin约束不回头是否可重复选看递归传i还是i 1只要数组有重复元素就先排序再在每层循环里跳过与前一个值相同的位置即可保证解集不重不漏。遇到重复元素 去重的面试手撕题组合、子集、排列是三大高频变体先排序、再判断是树层去重还是树枝去重基本就能稳定拿下。九、小结本题的核心价值不在凑 target本身而在于它是**重复元素下回溯去重最典型的载体**。一次理解i begin candidates[i] candidates[i - 1]这行代码就能同时吃透 40、90、47 三道 Medium 题的公共难点。刷完本文建议回到回溯算法章节目录按 39 → 40 → 78 → 90 → 46 → 47 的顺序巩固如需了解本仓库算法题集整体组织方式可查看精选力扣 300 道算法题使用指南。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐LeetCode 40 Combination Sum II组合总和 II全解法剖析排序去重回溯、频次映射与剪枝优化LeetCode 40 Combination Sum II组合总和 II全解法剖析排序去重回溯、频次映射与剪枝优化 导读 本文以仓库 articles/示例工程教程MAS 激活完全指南10 分钟免费搞定 Windows 与 Office 激活MAS 激活完全指南10 分钟免费搞定 Windows 与 Office 激活 打开弹窗就头疼MAS 帮你一次激活 Windows 和 Office Win操作系统GitHub_Trending/leetcode1/leetcode组合总和II回溯法的排序与去重GitHub_Trending/leetcode1/leetcode组合总和II回溯法的排序与去重 问题引入与核心挑战 在LeetCode算法题库中组合总和示例工程教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考