组合总和 II
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个候选人编号的集合 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次。
注意：解集不能包含重复的组合。
示例 1
示例 2
模拟答题者思考
1. 我先想暴力：从 candidates 中任选若干个（每个最多一次），枚举所有子集，检查总和是否等于 target——思路对，但组合爆炸，且输入有重复数字时会产生重复答案（如两个 1 分别选会生成相同组合）。
2. 重复在哪里？一是排列等价（[1,2,5] 与 [2,5,1]），用 start 只往后选可解决；二是相同数值的候选（如两个 1）在同一层被多次尝试，会生成重复组合。
3. 关键转化：先对 candidates 排序；每层从 start 往后选，递归传 i+1（不可重复选）；同层去重：若 i > start 且 candidates[i] == candidates[i-1] 则 continue，跳过等价分支。
4. 例 1 排序后 [1,1,2,5,6,7,10], target=8：第一层选第一个 1（remain=7）→ 再选第二个 1（remain=6）→ 选 6（remain=0）→ [1,1,6]；另一路选 1+2+5 等。
5. 与 #39 组合总和的区别：本题每个数只能用一次（传 i+1），且必须排序 + 同层去重；remain < 0 或 candidates[i] > remain 时剪枝。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
path | list<int> | 定义：当前正在构造的组合（已选数字序列） 维护：DFS 每层在末尾追加一个候选数，回溯时 pop 撤销更新：尝试 candidates[i] 时 append；该分支探索完毕后 pop |
remain | int | 定义：距离 target 还差多少和维护：每选一个数 x，子问题变为 remain - x更新： remain == 0 时收集答案；remain < 0 时剪枝返回 |
start | int | 定义：本轮可选候选的起始下标（含自身） 维护：只从 candidates[start..] 中选，保证组合不重复（如不会出现 [1,2,5] 与 [2,5,1]）更新：选 candidates[i] 后递归传 i+1（每个数最多用一次） |
ans | list<list<int>> | 定义：所有和为 target 的不同组合维护：仅当 remain == 0 时将 path 的副本加入更新：每到达合法叶子追加一次；中途不收集半成品 |
落码步骤
1. 对 candidates 排序，初始化结果 ans
2. 定义 DFS backtrack(start, remain, path)：若 remain == 0，将 path[:] 加入 ans 并返回；若 remain < 0 则剪枝返回
3. 对 i 从 start 到 len(candidates)-1：若 candidates[i] > remain 可 break；若 i > start 且 candidates[i] == candidates[i-1] 则 continue（同层去重）
4. 将 candidates[i] 追加到 path，递归 backtrack(i+1, remain - candidates[i], path)（传 i+1 保证每个数最多用一次）
5. 回溯：从 path 弹出末尾元素，继续尝试下一个 i
6. 从 backtrack(0, target, []) 启动，返回 ans
代码实现
class Solution:
def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
ans: list[list[int]] = []
candidates.sort()
def backtrack(start: int, remain: int, path: list[int]) -> None:
if remain == 0:
ans.append(path[:])
return
if remain < 0:
return
for i in range(start, len(candidates)):
if candidates[i] > remain:
break
if i > start and candidates[i] == candidates[i - 1]:
continue
path.append(candidates[i])
backtrack(i + 1, remain - candidates[i], path)
path.pop()
backtrack(0, target, [])
return ansclass Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> path;
sort(candidates.begin(), candidates.end());
function<void(int, int)> dfs = [&](int start, int remain) {
if (remain == 0) {
ans.push_back(path);
return;
}
if (remain < 0) return;
for (int i = start; i < (int)candidates.size(); i++) {
if (candidates[i] > remain) break;
if (i > start && candidates[i] == candidates[i - 1]) continue;
path.push_back(candidates[i]);
dfs(i + 1, remain - candidates[i]);
path.pop_back();
}
};
dfs(0, target);
return ans;
}
};
// 时间 O(2^N)，空间 O(N) 递归栈复杂度分析
O(2^N)（N 为候选数；排序 + 剪枝 + 同层去重后远好于全子集枚举）
O(N)（递归栈深度，不计输出）
常见坑
递归下标传 i 而非 i+1：本题每个数只能用一次，传 i 会重复选同一位置，产生非法组合。
忘记同层去重：输入 [1,1,2] 时，若不跳过 candidates[i]==candidates[i-1]（当 i>start），会输出两个 [1,2]。
去重条件写错：应写 i > start 时跳过，而非 i > 0；后者会误杀跨层合法分支（如两个 1 分属不同层时都需要）。
必测边界 Case
candidates = [3,4], target = 2 → []（最小候选已大于 target）
candidates = [5,2,2,1,2], target = 5 → 含 [5]
candidates = [10,1,2,7,6,1,5], target = 8 → 含 [1,1,6]（两个 1 来自不同位置，合法）
[2,5,2,1,2], target=5 → [[1,2,2],[5]]，排序去重后恰好两组
candidates = [1,1], target = 1 → [[1]]（只选其中一个 1，同层去重保证不重复）