企业官网建设流程全解析

• 文档
• 教程
• 知识库

本文基于 InterviewGuide 仓库中阿秀的刷题笔记（原题解析文档）展开，完整讲解力扣 40 题"组合总和 II"的经典回溯解法：为什么必须先排序、i > begin && candidates[i] == candidates[i-1]这一行去重代码的真正含义、以及"每个数字只能使用一次"与 39 题模板的差异。读完本文，你将掌握组合类回溯题的核心套路——树层去重，并能直接迁移到子集 II、全排列 II 等同类题目。

一、题目回顾：带重复元素的"凑 target"问题

给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。与 39 题最大的不同点有两个：

1. candidates可能包含重复数字；
2. 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(vector<int>& candidates, vector<vector<int>>& result, vector<int>& 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; // 剪枝 } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); // 去重前提 + 剪枝前提 vector<int> temp; vector<vector<int>> result; combinationSum2Core(candidates, result, temp, target, 0, 0); return result; }

递归函数的参数含义如下：

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(vector<int>& nums, vector<vector<int>>& result, vector<int>& temp, int index) { result.push_back(temp); // 子集：全部路径都要收集 unordered_map<int, 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_map<int, int> mp在每一层标记"同层次此元素已使用多次，再次使用必造成重复全排列，直接跳过"。可见**"层内去重"有两种工具：排序 + 相邻比较，或者哈希表记录**。前者省空间，后者不依赖排序（但本题的剪枝仍依赖排序，所以相邻比较法更贴合本场景）。

另一种常见的等价写法是用used[]布尔数组记录元素是否被使用过，配合used[i-1] == false判断同层重复，其去重效果与相邻比较法一致，读者可以根据习惯选择。

五、算法过程模拟：为什么[1, 1, 6]能被保留

以示例 1 排序后的candidates = [1, 1, 2, 5, 6, 7, 10]、target = 8为例，手动推演去重逻辑：

1. 第一层（begin = 0，sum = 0）：i = 0选1（i == begin，不去重），进入递归；i = 1时candidates[1] == candidates[0] == 1且i > begin，跳过，避免了第二个 1 作为"组合首元素"重复展开；i = 2选2……以此类推。
2. 第二层（从选1的分支进入，begin = 1，sum = 1）：此时i = 1 == begin，candidates[1] = 1不会被跳过，于是可以再选一个 1，得到temp = [1, 1]。这正是[1, 1, 6]的来源——同值元素出现在不同深度时被放行。
3. 剪枝：当sum + candidates[i] > 8时（如i指向10），直接return，不再展开。

可以看到，去重判断是"分层生效"的：begin的每次变化重置了"本层是否已选过该值"的上下文，这与哈希表法每层新建mp的原理完全一致。

六、与 39. 组合总和的完整对照

39 题的经典模板（仓库原笔记代码）如下，读者可逐行对比：

void combinationSumCore(vector<vector<int>>& res, vector<int>& candidates, int target, vector<int>& 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剪枝能显著压缩实际搜索空间。
• 空间复杂度：递归深度不超过n，temp长度同样不超过n，额外空间为O(n)（不计存储结果所需的空间）。
• 边界情况：
  • 若candidates中没有元素能凑出target，result为空，逻辑天然正确；
  • 若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+ 道算法题使用指南。

• 文档
• 教程
• 知识库