京公网安备11010502063487号给定一个可能含有重复数字的数组和一个目标值，找出所有和等于目标、并且每个数字只能使用一次的不重复组合。和上一题相比有两个变化：每个元素只能用一次（下一层要从 i + 1 开始），并且数组里有重复值，所以同样的组合可能从不同下标选出来，必须去重。标准的去重办法是先排序，然后在同一层里，遇到与前一个相同的数字就跳过。本文用真实数据展示不去重会出现多少重复的组合，实测暴力枚举子集和回溯的耗时，给出五种语言的实现，并把去重的判断做成分步演示。
完整题目见官方页面（链接在文末）。组合之间、组合内部的顺序都不作要求，核对时先把每个组合内部排序，再把所有组合排序后比较。基准解枚举全部 2^n 个子集，把和等于目标的子集排序后放进集合去重，与回溯是两种独立的写法。一共 12 组用例，覆盖：官方示例、大量重复值、目标不可达、全部相同的数字：
输入 [[10,1,2,7,6,1,5],8] 输出 [[1,1,6],[1,2,5],[1,7],[2,6]] 输入 [[2,5,2,1,2],5] 输出 [[1,2,2],[5]] 输入 [[1],1] 输出 [[1]] 输入 [[1],2] 输出 [] 输入 [[1,1,1,1],2] 输出 [[1,1]] 输入 [[1,1,1,1],5] 输出 []
数组排序后，相同的数字挨在一起。在同一层里，如果第 i 个数与第 i - 1 个相同，并且 i - 1 在这一层已经被尝试过，那么选第 i 个得到的所有组合，都已经在选第 i - 1 个时得到过了。不跳过的话，同一个组合会被多次记录。下面是不跳过的写法与 solve 的真实结果：
# 没有「同一层跳过相同的数」的写法 [10, 1, 2, 7, 6, 1, 5], target=8: 不去重得到 6 个（[[1, 1, 6], [1, 2, 5], [1, 7], [1, 2, 5], [1, 7], [2, 6]]） solve 得到 4 个 [2, 5, 2, 1, 2], target=5: 不去重得到 4 个（[[1, 2, 2], [1, 2, 2], [1, 2, 2], [5]]） solve 得到 2 个 [1, 1, 1, 1], target=2: 不去重得到 6 个（[[1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1]]） solve 得到 1 个
官方示例 [10, 1, 2, 7, 6, 1, 5] 目标 8：不去重得到 6 个结果，其中 [1, 2, 5] 和 [1, 7] 各出现了两次，正确答案只有 4 个；[1, 1, 1, 1] 目标 2 更极端：不去重得到 6 个一模一样的 [1, 1]（从 4 个 1 里选 2 个，C(4,2) = 6），正确答案只有 1 个。注意跳过的条件是 i > start，而不是 i > 0：start 是这一层的起点，同一层里的第一个数不应该被跳过，否则 [1, 1, 6] 这样的合法组合（用两个不同位置的 1）会丢掉。
先排序。dfs(start, remain) 从下标 start 开始选：remain 为 0 就收集；否则对每个 i：数字超过 remain 就结束这一层（已排序，后面的更大）；i > start 并且与前一个相同就跳过；否则选它，递归到 i + 1（每个数只用一次），返回后撤销。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(candidates, target): candidates = sorted(candidates) # 排序：让相同的数挨在一起，方便去重，也方便剪枝 res, path = [], [] def dfs(start, remain): if remain == 0: res.append(list(path)) return for i in range(start, len(candidates)): x = candidates[i] if x > remain: # 剪枝：已排序，后面的更大 break if i > start and x == candidates[i - 1]: # 同一层里，相同的数只作为"这一位"试一次，否则会得到重复的组合 continue path.append(x) dfs(i + 1, remain - x) # 每个数只能用一次：下一层从 i+1 开始 path.pop() dfs(0, target) return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[10,1,2,7,6,1,5],8] → [[1,1,6],[1,2,5],[1,7],[2,6]] [[2,5,2,1,2],5] → [[1,2,2],[5]] [[1],1] → [[1]] [[1],2] → [] [[1,1,1,1],2] → [[1,1]] [[1,1,1,1],5] → []
Java · 解法代码class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); // 排序：让相同的数挨在一起，方便去重，也方便剪枝 List<List<Integer>> res = new ArrayList<>(); dfs(candidates, 0, target, new ArrayList<>(), res); return res; } private void dfs(int[] cs, int start, int remain, List<Integer> path, List<List<Integer>> res) { if (remain == 0) { res.add(new ArrayList<>(path)); return; } for (int i = start; i < cs.length; i++) { if (cs[i] > remain) break; // 剪枝：已排序，后面的更大 if (i > start && cs[i] == cs[i - 1]) continue; // 同一层里，相同的数只试一次，否则会得到重复的组合 path.add(cs[i]); dfs(cs, i + 1, remain - cs[i], path, res); // 每个数只能用一次：下一层从 i+1 开始 path.remove(path.size() - 1); } } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[10,1,2,7,6,1,5],8] → [[1,1,6],[1,2,5],[1,7],[2,6]] [[2,5,2,1,2],5] → [[1,2,2],[5]] [[1],1] → [[1]] [[1],2] → [] [[1,1,1,1],2] → [[1,1]] [[1,1,1,1],5] → []
Go · 解法代码import "sort" func combinationSum2(candidates []int, target int) [][]int { sort.Ints(candidates) // 排序：让相同的数挨在一起，方便去重，也方便剪枝 res := [][]int{} path := []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 candidates[i] > remain { // 剪枝：已排序，后面的更大 break } if i > start && candidates[i] == candidates[i-1] { // 同一层里，相同的数只试一次，否则会得到重复的组合 continue } path = append(path, candidates[i]) dfs(i+1, remain-candidates[i]) // 每个数只能用一次：下一层从 i+1 开始 path = path[:len(path)-1] } } dfs(0, target) return res }
$ go build -o bin . && ./bin < cases.jsonl [[10,1,2,7,6,1,5],8] → [[1,1,6],[1,2,5],[1,7],[2,6]] [[2,5,2,1,2],5] → [[1,2,2],[5]] [[1],1] → [[1]] [[1],2] → [] [[1,1,1,1],2] → [[1,1]] [[1,1,1,1],5] → []
JavaScript · 解法代码function combinationSum2(candidates, target) { candidates.sort((a, b) => a - b); // 排序：让相同的数挨在一起，方便去重，也方便剪枝 const res = []; const path = []; const dfs = (start, remain) => { if (remain === 0) { res.push([...path]); return; } for (let i = start; i < candidates.length; i++) { if (candidates[i] > remain) break; // 剪枝：已排序，后面的更大 if (i > start && candidates[i] === candidates[i - 1]) continue; // 同一层里，相同的数只试一次 path.push(candidates[i]); dfs(i + 1, remain - candidates[i]); // 每个数只能用一次：下一层从 i+1 开始 path.pop(); } }; dfs(0, target); return res; }
$ node run.js < cases.jsonl [[10,1,2,7,6,1,5],8] → [[1,1,6],[1,2,5],[1,7],[2,6]] [[2,5,2,1,2],5] → [[1,2,2],[5]] [[1],1] → [[1]] [[1],2] → [] [[1,1,1,1],2] → [[1,1]] [[1,1,1,1],5] → []
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { void dfs(vector<int>& cs, int start, int remain, vector<int>& path, vector<vector<int>>& res) { if (remain == 0) { res.push_back(path); return; } for (int i = start; i < (int)cs.size(); i++) { if (cs[i] > remain) break; // 剪枝：已排序，后面的更大 if (i > start && cs[i] == cs[i - 1]) continue; // 同一层里，相同的数只试一次，否则会得到重复的组合 path.push_back(cs[i]); dfs(cs, i + 1, remain - cs[i], path, res); // 每个数只能用一次：下一层从 i+1 开始 path.pop_back(); } } public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); // 排序：让相同的数挨在一起，方便去重，也方便剪枝 vector<vector<int>> res; vector<int> path; dfs(candidates, 0, target, path, res); return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[10,1,2,7,6,1,5],8] → [[1,1,6],[1,2,5],[1,7],[2,6]] [[2,5,2,1,2],5] → [[1,2,2],[5]] [[1],1] → [[1]] [[1],2] → [] [[1,1,1,1],2] → [[1,1]] [[1,1,1,1],5] → []
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
数组长度分别为 10、14、18、22，元素由 1 到 5 循环得到（重复值很多），目标等于数组长度，每个规模取三次中最快的一次：
数组长度 n（重复值很多，target = n） | 暴力解 | 本文解法
10 | 0.525 ms | 0.012 ms
14 | 11.427 ms | 0.035 ms
18 | 222.324 ms | 0.092 ms
22 | （未测，太慢） | 0.211 ms枚举全部子集的耗时随长度每增加 4 大约乘 16（2 的 4 次方）：从 10 到 14 增长约 21.8 倍，从 14 到 18 增长约 19.5 倍，与 2^n 一致，所以长度 22 没有再测。回溯加剪枝的耗时（0.012ms 到 0.211ms）增长要平缓得多，因为它只探索和不超过目标的前缀，并且重复值被合并了。n = 18 时，暴力 222.3ms，回溯 0.092ms，约 2400 倍。这批数据是我自己造的（值域只有 1 到 5，目标为 n），换一批数据倍数会不同。
Python 版本另外和枚举子集的基准做了随机对拍，数组长度 1 到 12、取值 1 到 6，重复值很多：
随机对拍 5000 组（长度 1 到 12、取值 1 到 6 的随机数组（重复值很多），target 取 1 到 15；结果按集合比较），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [10, 1, 2, 7, 6, 1, 5]，目标 8，排序后是 [1, 1, 2, 5, 6, 7, 10]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的组合集合与 solve 的返回值一致。注意第一层里选了下标 0 的 1 之后，再遇到下标 1 的 1，因为它与同层前一个相同，被整个跳过（淡色）；但在下一层里，下标 1 的 1 是这一层的第一个，不会被跳过，所以 [1, 1, 6] 这个用了两个 1 的组合仍然能找到。