40. 组合总和 II
题目描述
输入整数数组 candidates 和整数 target。candidates 中可能有相同的数。
从 candidates 中选出若干个位置的数，使它们之和等于 target。每个位置上的数在一个组合中最多用一次。
返回所有符合要求的组合。元素相同（不计顺序）的组合只能出现一次。组合的返回顺序不限。
示例 1
输入：candidates = [10,1,2,7,6,1,5], target = 8 输出：[[1,1,6],[1,2,5],[1,7],[2,6]]
解释：两个 1 可以和 6 组成 [1,1,6]；用不同位置的 1 得到的 [1,7] 只算一个。
示例 2
输入：candidates = [2,5,2,1,2], target = 5 输出：[[1,2,2],[5]]
解释：三个 2 中选两个和 1 组成 [1,2,2]，另有 [5]。
数据范围
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
解题思路：排序 + 回溯（同层跳过重复）
先排序，让相同的数挨在一起。dfs(start, remain) 在 candidates[start:] 中为当前位置挑一个数：同一层里相同的数只试第一个，这样不会生成重复组合；一旦当前数大于 remain，后面的数更大，直接 break。选了 candidates[i] 后从 i+1 继续，保证每个位置只用一次。
为什么正确
path 是升序的且和为 target - remain；同一层中每个不同的值只作为开头尝试一次。
复杂度分析
时间最坏 O(n · 2^n)，空间 O(n) 递归栈（不计输出）。
易错点
去重条件是 i > start 而不是 i > 0。写成 i > 0 会把“下一层选第二个相同值”也跳过，漏掉 [1,1,6] 这类组合。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
res, path = [], []
def dfs(start, remain):
if remain == 0:
res.append(path[:])
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue
if candidates[i] > remain:
break
path.append(candidates[i])
dfs(i + 1, remain - candidates[i])
path.pop()
dfs(0, target)
return resclass Solution {
int[] candidates;
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
this.candidates = candidates;
dfs(0, target);
return res;
}
void dfs(int start, int remain) {
if (remain == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
if (candidates[i] > remain) {
break;
}
path.add(candidates[i]);
dfs(i + 1, remain - candidates[i]);
path.remove(path.size() - 1);
}
}
}class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> res;
vector<int> path;
function<void(int, int)> dfs = [&](int start, int remain) {
if (remain == 0) {
res.push_back(path);
return;
}
for (int i = start; i < (int)candidates.size(); i++) {
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
if (candidates[i] > remain) {
break;
}
path.push_back(candidates[i]);
dfs(i + 1, remain - candidates[i]);
path.pop_back();
}
};
dfs(0, target);
return res;
}
};func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
res, path := [][]int{}, []int{}
var dfs func(start, remain int)
dfs = func(start, remain int) {
if remain == 0 {
res = append(res, append([]int{}, path...))
return
}
for i := start; i < len(candidates); i++ {
if i > start && candidates[i] == candidates[i-1] {
continue
}
if candidates[i] > remain {
break
}
path = append(path, candidates[i])
dfs(i+1, remain-candidates[i])
path = path[:len(path)-1]
}
}
dfs(0, target)
return res
}var combinationSum2 = function(candidates, target) {
candidates.sort((a, b) => a - b);
const res = [], path = [];
const dfs = (start, remain) => {
if (remain === 0) {
res.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (i > start && candidates[i] === candidates[i - 1]) {
continue;
}
if (candidates[i] > remain) {
break;
}
path.push(candidates[i]);
dfs(i + 1, remain - candidates[i]);
path.pop();
}
};
dfs(0, target);
return res;
};function combinationSum2(candidates: number[], target: number): number[][] {
candidates.sort((a, b) => a - b);
const res: number[][] = [], path: number[] = [];
const dfs = (start: number, remain: number): void => {
if (remain === 0) {
res.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (i > start && candidates[i] === candidates[i - 1]) {
continue;
}
if (candidates[i] > remain) {
break;
}
path.push(candidates[i]);
dfs(i + 1, remain - candidates[i]);
path.pop();
}
};
dfs(0, target);
return res;
}其他解法
主解法在排序数组上逐个元素决策，用 i > start 且与前一个相同时跳过来去重；分组计数法把相同数值合并，每层枚举选几个，去重由结构保证。两者最坏复杂度相同。
解法 2：按数值分组计数的回溯 时间 O(2^n·n)，空间 O(n)
先统计每个不同数值 v 出现的次数 cnt，并按数值升序排列。递归时每一层只决定一个数值：选 0 个、1 个……最多 min(cnt, remain / v) 个，然后进入下一个数值。因为同一数值只在一层里按“个数”枚举，天然不会产生重复组合；当前数值大于剩余目标时直接剪枝。
去重逻辑从“同层跳过相同元素”变成“按值分组、枚举个数”，更容易证明不重复，且递归深度只取决于不同数值的个数。缺点是需要额外的计数表，回溯时要一次弹出多个元素。
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
freq = sorted(Counter(candidates).items())
res, path = [], []
def dfs(k, remain):
if remain == 0:
res.append(path[:])
return
if k == len(freq) or freq[k][0] > remain:
return
dfs(k + 1, remain)
v, cnt = freq[k]
most = min(cnt, remain // v)
for t in range(1, most + 1):
path.append(v)
dfs(k + 1, remain - t * v)
for _ in range(most):
path.pop()
dfs(0, target)
return resclass Solution {
List<int[]> freq = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
for (int x : candidates) {
if (freq.isEmpty() || freq.get(freq.size() - 1)[0] != x) freq.add(new int[]{x, 1});
else freq.get(freq.size() - 1)[1]++;
}
dfs(0, target);
return res;
}
void dfs(int k, int remain) {
if (remain == 0) { res.add(new ArrayList<>(path)); return; }
if (k == freq.size() || freq.get(k)[0] > remain) return;
dfs(k + 1, remain);
int v = freq.get(k)[0];
int most = Math.min(freq.get(k)[1], remain / v);
for (int t = 1; t <= most; t++) {
path.add(v);
dfs(k + 1, remain - t * v);
}
for (int t = 0; t < most; t++) path.remove(path.size() - 1);
}
}class Solution {
public:
vector<pair<int, int>> freq;
vector<vector<int>> res;
vector<int> path;
void dfs(int k, int remain) {
if (remain == 0) { res.push_back(path); return; }
if (k == (int)freq.size() || freq[k].first > remain) return;
dfs(k + 1, remain);
int v = freq[k].first;
int most = min(freq[k].second, remain / v);
for (int t = 1; t <= most; t++) {
path.push_back(v);
dfs(k + 1, remain - t * v);
}
for (int t = 0; t < most; t++) path.pop_back();
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
freq.clear(); res.clear(); path.clear();
for (int x : candidates) {
if (freq.empty() || freq.back().first != x) freq.push_back({x, 1});
else freq.back().second++;
}
dfs(0, target);
return res;
}
};func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
freq := [][2]int{}
for _, x := range candidates {
if len(freq) == 0 || freq[len(freq)-1][0] != x {
freq = append(freq, [2]int{x, 1})
} else {
freq[len(freq)-1][1]++
}
}
res, path := [][]int{}, []int{}
var dfs func(k, remain int)
dfs = func(k, remain int) {
if remain == 0 {
res = append(res, append([]int{}, path...))
return
}
if k == len(freq) || freq[k][0] > remain {
return
}
dfs(k+1, remain)
v := freq[k][0]
most := min(freq[k][1], remain/v)
for t := 1; t <= most; t++ {
path = append(path, v)
dfs(k+1, remain-t*v)
}
path = path[:len(path)-most]
}
dfs(0, target)
return res
}var combinationSum2 = function(candidates, target) {
candidates.sort((a, b) => a - b);
const freq = [];
for (const x of candidates) {
if (!freq.length || freq[freq.length - 1][0] !== x) freq.push([x, 1]);
else freq[freq.length - 1][1]++;
}
const res = [], path = [];
const dfs = (k, remain) => {
if (remain === 0) { res.push([...path]); return; }
if (k === freq.length || freq[k][0] > remain) return;
dfs(k + 1, remain);
const v = freq[k][0];
const most = Math.min(freq[k][1], Math.floor(remain / v));
for (let t = 1; t <= most; t++) {
path.push(v);
dfs(k + 1, remain - t * v);
}
path.length -= most;
};
dfs(0, target);
return res;
};function combinationSum2(candidates: number[], target: number): number[][] {
candidates.sort((a, b) => a - b);
const freq: number[][] = [];
for (const x of candidates) {
if (!freq.length || freq[freq.length - 1][0] !== x) freq.push([x, 1]);
else freq[freq.length - 1][1]++;
}
const res: number[][] = [], path: number[] = [];
const dfs = (k: number, remain: number): void => {
if (remain === 0) { res.push([...path]); return; }
if (k === freq.length || freq[k][0] > remain) return;
dfs(k + 1, remain);
const v = freq[k][0];
const most = Math.min(freq[k][1], Math.floor(remain / v));
for (let t = 1; t <= most; t++) {
path.push(v);
dfs(k + 1, remain - t * v);
}
path.length -= most;
};
dfs(0, target);
return res;
}