LeetCode LCR 082. 组合总和 II
目录
题目描述
题意分析
给一个可能含有重复元素的正整数数组
candidates和目标值target，找出所有和恰好为target的组合。与上一题的两处差别是本题的全部难度来源：数组里允许出现相同的值，而每个数组位置最多只能被使用一次。
「每个位置只能用一次」和「答案中不能出现重复组合」是两件不同的事，必须分开理解。前者是对下标的限制：下标 3 用过了就不能再用。后者是对值的多重集的限制：如果数组里有两个 1，那么
[1(下标1), 7]和[1(下标5), 7]是两个不同的下标选法，但它们的值序列同为[1,7]，只能输出一次。这两个约束需要两套不同的机制来满足。
约束规模：数组长度不超过 100，元素在
[1, 50]之间，target不超过 30。元素全为正这一点再次给出剪枝信号——路径和单调递增，超过target即可整支砍掉。而元素可能大于target（最大 50 对 30），说明必须允许「一个都选不上」的情况，答案可以为空。
边界要覆盖：全部元素相同（例如
[1,1,1,1]）时去重压力最大；target小于最小元素时无解返回空列表；单个元素恰好等于target时应产出长度为 1 的组合；同一个值出现多次且答案确实需要用到其中的两份（例如[1,1,6]用掉了两个 1），说明不能简单地把重复值整体去掉。
解法：回溯搜索
核心思路
沿用组合搜索的骨架：递归函数带一个「本层允许选取的最小下标」
u，横向枚举i从u到末尾，选中i后向下传i + 1。传i + 1直接满足了「每个位置只用一次」，同时下标严格递增又保证不会把同一批元素以不同顺序枚举两遍。
但这还不够。以
[1, 1, 6]、target = 7为例：下标 0 的 1 配上 6 得到[1,6]，下标 1 的 1 配上 6 也得到[1,6]，两条路径的下标不同、值完全相同，答案重复了。瓶颈在于同一层里若干个相同的值会各自开出一棵形状完全一样的子树。
关键观察：先把数组排序，让相同的值相邻。这时上面的重复现象有了精确刻画——在同一层的横向枚举中，若
candidates[i] == candidates[i-1]且i > u，那么下标i开出的子树与下标i-1开出的子树完全同构，因为它们本层选的值相同，而剩余可选区间[i+1, n)是[i, n)的子集，前者能生成的每一个组合后者都能生成。既然如此，让相同值在同一层只由第一个下标代表即可。
于是不变量是：
t中的下标严格递增，s恒等于t的元素之和，且任意一层横向枚举中，同一个值只被选中一次。条件里的i > u至关重要——i == u说明这是本层第一次遇到这个值，必须保留；i > u才是「本层已经用同样的值试过一遍」的情形。注意判断的是「同层重复」而不是「路径中不能有重复值」，所以[1,1,6]这种在不同层各取一个 1 的答案依然能被搜到。
解题步骤
- 先排序：
Arrays.sort(candidates)。排序不是为了剪枝方便，而是去重逻辑成立的前提——只有相同的值挨在一起，candidates[i] == candidates[i - 1]才能等价于「本层已经试过这个值」。不排序的话[1,6,1]里两个 1 不相邻，去重条件完全失效。
- 超额剪枝前置：进入递归先判
s > target就返回。元素全为正，路径和只增不减，这一支不可能再回到target。
- 命中即收：
s == target时深拷贝t存入answer并返回。此处return也是一种剪枝：既然已经等于target，再选任何正数都会超额。
- 同层去重：
if (i > u && candidates[i] == candidates[i - 1]) continue;。判断条件必须是i > u而不是i > 0——i > 0会把「本层第一次遇到该值」的情形也一并跳过，导致[1,1,6]这类需要重复取值的答案彻底丢失。
- 选择、递归、撤销：
t.add之后调用dfs(i + 1, s + candidates[i], t)，回来再t.remove。传i + 1而非i，对应「每个位置只能用一次」；这是与上一题唯一的一字之差。
以
candidates = [2, 5, 2, 1, 2]、target = 5走一遍。排序后数组变为[1, 2, 2, 2, 5]，下标 0 到 4。
根节点
dfs(u=0, s=0, t=[])，横向枚举i从 0 到 4。
i = 0选 1，进入dfs(u=1, s=1, t=[1])。这一层i = 1选 2，进入dfs(u=2, s=3, t=[1,2])；该层i = 2时i == u，是本层第一次见到 2，保留，s = 3 + 2 = 5命中，记下第一个答案[1,2,2]；接着i = 3满足i > u且candidates[3] == candidates[2]，跳过——如果不跳，会再产出一个一模一样的[1,2,2]；i = 4选 5 得s = 8，下一层入口判s > target返回。
回到
dfs(u=1, s=1, t=[1])继续横向：i = 2时i > u = 1且值与前一个相同，跳过；i = 3同理跳过；i = 4选 5 得s = 6，超额返回。这一支结束。
回到根节点：
i = 1选 2，进入dfs(u=2, s=2, t=[2])，其下选 2 得s = 4，再往下i = 3因同层重复被跳过、i = 4得 9 超额，无解；回到该层i = 3同层重复跳过，i = 4得 7 超额。整支无解。
根节点
i = 2：i > u = 0且candidates[2] == candidates[1]，跳过；i = 3同理跳过——这两次跳过挡掉的正是与i = 1完全同构的两棵子树。i = 4选 5，s = 5命中，记下第二个答案[5]。
最终
answer = [[1,2,2],[5]]。若把去重条件写成i > 0，根节点的i = 1之后一切以 2 开头的分支都会被砍掉，[1,2,2]中层内的第二个 2 也选不到，答案会退化成只剩[5]。
代码实现
class Solution {
private List<List<Integer>> answer;
private int[] candidates;
private int target;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
answer = new ArrayList<>();
// 排序让相同值相邻，是同层去重条件成立的前提。
Arrays.sort(candidates);
this.target = target;
this.candidates = candidates;
dfs(0, 0, new ArrayList<>());
return answer;
}
// u：本层允许选取的最小下标；s：当前路径和；t：当前路径。
private void dfs(int u, int s, List<Integer> t) {
if (s > target) {
return;
}
if (s == target) {
answer.add(new ArrayList<>(t));
return;
}
for (int i = u; i < candidates.length; ++i) {
// 同层遇到重复值只保留第一个；条件必须是 i > u 而不是 i > 0。
if (i > u && candidates[i] == candidates[i - 1]) {
continue;
}
t.add(candidates[i]);
// 传 i + 1：每个下标最多使用一次。
dfs(i + 1, s + candidates[i], t);
t.remove(t.size() - 1);
}
}
}
func combinationSum2(candidates []int, target int) [][]int {
var answer [][]int
var t []int
// 排序让相同值相邻，是同层去重条件成立的前提。
sort.Ints(candidates)
// u：本层允许选取的最小下标；s：当前路径和；t：当前路径。
var dfs func(u, s int, t []int)
dfs = func(u, s int, t []int) {
if s > target {
return
}
if s == target {
answer = append(answer, slices.Clone(t))
return
}
for i := u; i < len(candidates); i++ {
// 同层遇到重复值只保留第一个；条件必须是 i > u 而不是 i > 0。
if i > u && candidates[i] == candidates[i-1] {
continue
}
t = append(t, candidates[i])
// 传 i+1：每个下标最多使用一次。
dfs(i+1, s+candidates[i], t)
t = t[:len(t)-1]
}
}
dfs(0, 0, t)
return answer
}
复杂度分析
- 时间复杂度：$O(2^n \times n)$ 的最坏上界，其中 $n$ 是数组长度。每个下标选或不选构成 $2^n$ 条路径，命中时拷贝长度为 $O(n)$ 的路径。排序的 $O(n \log n)$ 被这一项吞掉。实际运行中「超额剪枝」与「同层去重」会砍掉绝大部分子树，本题 $n \le 100$ 而 $target \le 30$，路径深度最多 30 层，远达不到上界。
- 空间复杂度：$O(n)$，递归栈深度不超过数组长度，路径
t的长度与之同阶。排序若为原地实现不额外占用，返回值按惯例不计入。
关键点总结
- 「同层去重」是处理带重复元素的组合问题的标准武器：排序后在横向枚举中跳过与前一个相同的值。这个模式在子集 II、全排列 II 里以不同变体反复出现，值得当作肌肉记忆。
i > u与i > 0的区别是本题的分水岭，也是面试官最爱追问的一点：前者跳过的是「同一层的重复」，后者会误伤「不同层各取一个相同值」的合法答案。能讲清这个区别，基本就说明真正理解了去重发生在哪个维度。- 「位置不可复用」和「组合不可重复」是两个正交的约束，分别由「递归传
i + 1」和「同层跳过相同值」解决。把它们拆开讲，比笼统地说「去重」更有说服力。- 排序是去重逻辑的前置条件，不是可选优化。任何依赖「相邻相同」的判断，都必须先保证有序。
- 可迁移的判断法：面对「输出所有方案且不能重复」的题，先问自己重复来自哪里——是元素顺序造成的，就用下标单调；是相同值造成的，就用同层跳过。两种来源可以叠加，本题正是叠加的典型。
易错点总结
- 忘记排序：
candidates = [1,6,1]、target = 7时两个 1 不相邻，去重条件一次都不触发，答案会输出两个完全相同的[1,6]。- 去重条件写成
i > 0：candidates = [1,1,6]、target = 8会丢掉[1,1,6]，因为第二个 1 在下一层被误判为重复，结果变成空列表。- 递归传
i而不是i + 1：candidates = [2,5]、target = 6会产出[2,2,2]，但数组里只有一个 2，属于凭空复用同一个位置。- 忘记
t.remove(t.size() - 1)：candidates = [1,2,5]、target = 6时失败路径[1,2]的残留会带进兄弟分支，产出[1,2,5]这种和为 8 的非法答案。- 把
t的引用直接放进answer：candidates = [1,2,2,2,5]、target = 5最终会得到[[],[]]，因为搜索结束时共享的t已被回溯清空。- Go 里写
answer = append(answer, t)而不是slices.Clone(t)：[1,2,2]存入后其底层数组会被兄弟分支的append覆写，输出变成乱值。- 只判
s == target而漏掉s > target：candidates为 100 个 1、target = 30时搜索不再被截断，会一路下探到数组末尾，运行时间从毫秒级涨到超时。- 把两个判断合并成
s >= target一次返回：candidates = [5]、target = 5时不再记录答案，输出空列表。- 试图用
Set<List<Integer>>事后去重代替同层跳过：candidates全是 1 且长度 100 时，搜索树规模丝毫不减，仍然超时，而且面试中会被认为没找到重复的根因。- 误以为可以先把重复值压缩成「值 + 个数」再做无重复的组合搜索：
candidates = [1,1,6]、target = 8若把两个 1 合并成一个，就选不出需要两份 1 的答案；压缩后必须额外枚举每个值取用几份，反而比同层跳过更复杂。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 40. 组合总和 II | 中等 | 与本题完全同题，代码可原样提交 |
| 39. 组合总和 | 中等 | 元素互不相同但可无限复用，递归传 i 且不需要同层去重 |
| LCR 081. 组合总和 | 中等 | 与 39 同题，与本题对照可看清「传 i」与「传 i+1」的分工 |
| 90. 子集 II | 中等 | 同样的排序加同层去重，但没有和的约束，每个节点都直接是答案 |
| 47. 全排列 II | 中等 | 去重目标从组合换成排列，需借 used 数组判断前一个相同值是否已用 |
| 77. 组合 | 中等 | 元素天然互不相同，只需下标递增，是本题剥掉去重逻辑后的骨架 |
| 216. 组合总和 III | 中等 | 候选固定为 1~9 且无重复，改为同时约束元素个数与总和 |
| LCR 080. 组合 | 中等 | 与 77 同题，可作为练习下标递增模板的最简入口 |