京公网安备11010502063487号给定一组互不相同的正整数候选数和一个目标值，找出所有和等于目标的组合，同一个数字可以无限次使用，组合不同的判定是"某个数字使用的次数不同"（[2, 3] 和 [3, 2] 是同一个组合）。做法是回溯，关键有两个细节：递归时下一层仍从当前下标开始（因为允许重复使用），且不回头选前面的数（避免同一个组合被排列成多种顺序）。本文用真实数据展示"每层都从头选"会得到多少重复的排列，实测两种做法的耗时，给出五种语言的实现，并把递归的过程做成分步演示。
完整题目见官方页面（链接在文末）。组合之间、组合内部的顺序都不作要求，核对时先把每个组合内部排序，再把所有组合排序后比较。基准解依次决定"第 i 个候选数用几次"，是与"边走边选"的回溯完全不同的写法。一共 12 组用例，覆盖：官方示例、目标无法凑出、目标比所有候选都小、候选只有一个、候选大于目标：
输入 [[2,3,6,7],7] 输出 [[7],[2,2,3]] 输入 [[2,3,5],8] 输出 [[3,5],[2,3,3],[2,2,2,2]] 输入 [[2],1] 输出 [] 输入 [[2],4] 输出 [[2,2]] 输入 [[1],3] 输出 [[1,1,1]] 输入 [[7,3,2],18] 输出 [[2,2,2,2,2,2,2,2,2],[2,2,2,2,2,2,3,3],[2,2,2,3,3,3,3],[3,3,3,3,3,3],[2,2,2,2,3,7],[2,3,3,3,7],[2,2,7,7]]
如果回溯每一层都从第 0 个候选数开始选，那么 [2, 2, 3]、[2, 3, 2]、[3, 2, 2] 会被当作三个不同的答案。下面是这种写法与 solve 的真实结果：
# 每层都从头选（没有 start 下标）的写法：同一个组合的所有排列都会出现 [2, 3, 6, 7], target=7: 每层从头选得到 4 个 solve 得到 2 个 [2, 3, 5], target=8: 每层从头选得到 6 个 solve 得到 3 个 [2, 3, 5, 7], target=12: 每层从头选得到 35 个 solve 得到 7 个 [2, 3, 6, 7], 7 每层从头选的具体结果：[[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]]
[2, 3, 6, 7] 目标 7：每层从头选得到 4 个（[2, 2, 3] 的三种排列加上 [7]），正确答案只有 2 个组合。候选数越多，重复越严重：[2, 3, 5, 7] 目标 12，每层从头选得到 35 个，正确答案只有 7 个。解决办法是递归时传入下标 start，只允许选下标不小于 start 的数，这样每个组合只会以不降序的顺序出现一次。
先把候选数排序。dfs(start, remain) 表示还需要凑 remain，可以选下标不小于 start 的候选数。remain 为 0 时收集当前路径；否则从 start 开始依次尝试候选数 x：如果 x 大于 remain，由于已排序，后面的更大，直接结束这一层；否则选它，递归时传 i（不是 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)): # 只往后选（i 从 start 开始），保证组合里数字不降序，不会出现 [2,3] 和 [3,2] 重复 x = candidates[i] if x > remain: # 剪枝：已排序，后面的更大 break path.append(x) dfs(i, remain - x) # 传 i 而不是 i+1：同一个数字可以重复使用 path.pop() dfs(0, target) return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[2,3,6,7],7] → [[2,2,3],[7]] [[2,3,5],8] → [[2,2,2,2],[2,3,3],[3,5]] [[2],1] → [] [[2],4] → [[2,2]] [[1],3] → [[1,1,1]] [[7,3,2],18] → [[2,2,2,2,2,2,2,2,2],[2,2,2,2,2,2,3,3],[2,2,2,2,3,7],[2,2,2,3,3,3,3],[2,2,7,7],[2,3,3,3,7],[3,3,3,3,3,3]]
Java · 解法代码class Solution { public List<List<Integer>> combinationSum(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++) { // 只往后选，保证组合里数字不降序，不会出现 [2,3] 和 [3,2] 重复 if (cs[i] > remain) break; // 剪枝：已排序，后面的更大 path.add(cs[i]); dfs(cs, i, remain - cs[i], path, res); // 传 i 而不是 i+1：同一个数字可以重复使用 path.remove(path.size() - 1); } } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[2,3,6,7],7] → [[2,2,3],[7]] [[2,3,5],8] → [[2,2,2,2],[2,3,3],[3,5]] [[2],1] → [] [[2],4] → [[2,2]] [[1],3] → [[1,1,1]] [[7,3,2],18] → [[2,2,2,2,2,2,2,2,2],[2,2,2,2,2,2,3,3],[2,2,2,2,3,7],[2,2,2,3,3,3,3],[2,2,7,7],[2,3,3,3,7],[3,3,3,3,3,3]]
Go · 解法代码import "sort" func combinationSum(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++ { // 只往后选，保证组合里数字不降序，不会出现 [2,3] 和 [3,2] 重复 if candidates[i] > remain { // 剪枝：已排序，后面的更大 break } path = append(path, candidates[i]) dfs(i, remain-candidates[i]) // 传 i 而不是 i+1：同一个数字可以重复使用 path = path[:len(path)-1] } } dfs(0, target) return res }
$ go build -o bin . && ./bin < cases.jsonl [[2,3,6,7],7] → [[2,2,3],[7]] [[2,3,5],8] → [[2,2,2,2],[2,3,3],[3,5]] [[2],1] → [] [[2],4] → [[2,2]] [[1],3] → [[1,1,1]] [[7,3,2],18] → [[2,2,2,2,2,2,2,2,2],[2,2,2,2,2,2,3,3],[2,2,2,2,3,7],[2,2,2,3,3,3,3],[2,2,7,7],[2,3,3,3,7],[3,3,3,3,3,3]]
JavaScript · 解法代码function combinationSum(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++) { // 只往后选，保证组合里数字不降序，不会出现 [2,3] 和 [3,2] 重复 if (candidates[i] > remain) break; // 剪枝：已排序，后面的更大 path.push(candidates[i]); dfs(i, remain - candidates[i]); // 传 i 而不是 i+1：同一个数字可以重复使用 path.pop(); } }; dfs(0, target); return res; }
$ node run.js < cases.jsonl [[2,3,6,7],7] → [[2,2,3],[7]] [[2,3,5],8] → [[2,2,2,2],[2,3,3],[3,5]] [[2],1] → [] [[2],4] → [[2,2]] [[1],3] → [[1,1,1]] [[7,3,2],18] → [[2,2,2,2,2,2,2,2,2],[2,2,2,2,2,2,3,3],[2,2,2,2,3,7],[2,2,2,3,3,3,3],[2,2,7,7],[2,3,3,3,7],[3,3,3,3,3,3]]
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++) { // 只往后选，保证组合里数字不降序，不会出现 [2,3] 和 [3,2] 重复 if (cs[i] > remain) break; // 剪枝：已排序，后面的更大 path.push_back(cs[i]); dfs(cs, i, remain - cs[i], path, res); // 传 i 而不是 i+1：同一个数字可以重复使用 path.pop_back(); } } public: vector<vector<int>> combinationSum(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 [[2,3,6,7],7] → [[2,2,3],[7]] [[2,3,5],8] → [[2,2,2,2],[2,3,3],[3,5]] [[2],1] → [] [[2],4] → [[2,2]] [[1],3] → [[1,1,1]] [[7,3,2],18] → [[2,2,2,2,2,2,2,2,2],[2,2,2,2,2,2,3,3],[2,2,2,2,3,7],[2,2,2,3,3,3,3],[2,2,7,7],[2,3,3,3,7],[3,3,3,3,3,3]]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
候选数固定为 [2, 3, 5, 7]，目标从 20 增大到 80，每个规模取三次中最快的一次，基准解不做排序剪枝：
target | 暴力解 | 本文解法
20 | 0.051 ms | 0.019 ms
40 | 0.331 ms | 0.143 ms
60 | 1.182 ms | 0.542 ms
80 | （未测，太慢） | 1.472 ms排序加剪枝的回溯比基准快约 2 到 3 倍（例如目标 60 时 0.54ms 对 1.18ms），二者都随目标的增大而快速增长，因为组合个数本身在快速增长。基准解在目标 80 时没有再测。这里的差距只反映"剪枝省掉了一些没有意义的尝试"，不能说明复杂度上有本质的不同：结果个数决定了下界。
Python 版本另外和基准解做了随机对拍：
随机对拍 10000 组（1 到 4 个互不相同的候选数（取值 1 到 8），target 取 1 到 15；结果按集合比较（组合之间、组合内部的顺序不要求）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [2, 3, 6, 7]，目标 7。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的组合集合与 solve 的返回值一致。先一路选 2：[2]、[2, 2]、[2, 2, 2]，剩余 1，下一个候选 2 已经大于 1，剪枝返回；然后 [2, 2, 3] 凑成 7，记录。