京公网安备11010502063487号给定两个整数 n 和 k，返回从 1 到 n 中选 k 个数的所有组合，顺序不限。这是回溯的另一道基础题，与全排列的区别是：[1, 2] 和 [2, 1] 是同一个组合，所以每次选数只能选比上一个数更大的，用一个 start 指针记录下一个可选数字的起点。它有一个非常实用的优化：剪枝——如果剩下的数字已经不够凑满 k 个，就不用继续尝试了。本文用真实的递归调用次数展示剪枝的效果（有时是 5000 倍），实测回溯与标准库的耗时，给出五种语言的实现，并把选数过程做成分步演示。
完整题目见官方页面（链接在文末）。组合的输出顺序不作要求，核对时按集合比较（每个组合内部排序）。基准解是 Python 标准库的 itertools.combinations，与手写回溯是两种独立的实现。一共 12 组用例，覆盖：官方示例、k = 1、k = n、n = k = 1、一般规模：
输入 [4,2] 输出 [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] 输入 [1,1] 输出 [[1]] 输入 [5,3] 输出 [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]] 输入 [5,5] 输出 [[1,2,3,4,5]] 输入 [5,1] 输出 [[1],[2],[3],[4],[5]] 输入 [6,3] 输出 [[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,3,4],[1,3,5],[1,3,6],[1,4,5],[1,4,6],[1,5,6],[2,3,4],[2,3,5],[2,3,6],[2,4,5],[2,4,6],[2,5,6],[3,4,5],[3,4,6],[3,5,6],[4,5,6]]
不剪枝的回溯，每一层都从 start 试到 n。但如果还需要选 need 个数，而 i 之后（包括 i）只剩下不到 need 个数，这条路一定凑不满 k 个，只会白白递归下去。所以 i 最大只需要试到 n - need + 1。下面是真实统计的递归调用次数，对比不剪枝和剪枝：
递归调用次数：不剪枝 vs 剪枝（i 最大只到 n-need+1） n=10, k= 5: 不剪枝 638 次 剪枝 462 次 结果个数 252 不剪枝是剪枝的 1.38 倍 n=16, k= 8: 不剪枝 39203 次 剪枝 24310 次 结果个数 12870 不剪枝是剪枝的 1.61 倍 n=20, k= 3: 不剪枝 1351 次 剪枝 1330 次 结果个数 1140 不剪枝是剪枝的 1.02 倍 n=20, k=17: 不剪枝 1048365 次 剪枝 5985 次 结果个数 1140 不剪枝是剪枝的 175.17 倍 n=20, k=19: 不剪枝 1048575 次 剪枝 210 次 结果个数 20 不剪枝是剪枝的 4993.21 倍
剪枝的效果取决于 k：n = 10, k = 5 时只减少了约 28%（638 次对 462 次）；n = 20, k = 3 时几乎没有区别（1351 次对 1330 次）；但 k 接近 n 时差距极大：n = 20, k = 17 时不剪枝要 1048365 次，剪枝只要 5985 次，约 175 倍；n = 20, k = 19 时 1048575 次对 210 次，约 4993 倍。原因是不剪枝的回溯会先枚举出所有前缀，再发现凑不满，而 k 接近 n 时几乎所有前缀都凑不满。两种做法得到的结果个数是一样的（例如 n = 20, k = 19 只有 20 个组合）。
dfs(start)：先算还需要选几个数 need = k - len(path)；need 为 0 就收集一份 path 的副本；否则枚举 i 从 start 到 n - need + 1：把 i 加入 path，递归 dfs(i + 1)（下一个只能选更大的），返回后撤销。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(n, k): res, path = [], [] def dfs(start): need = k - len(path) # 还需要再选几个数 if need == 0: res.append(path[:]) return for i in range(start, n - need + 2): # 剪枝：i 之后（含 i）至少还要剩下 need 个数，所以 i 最大是 n - need + 1 path.append(i) dfs(i + 1) # 只往后选，保证组合里数字递增，不会出现 [1,2] 和 [2,1] 重复 path.pop() dfs(1) return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [4,2] → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] [1,1] → [[1]] [5,3] → [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]] [5,5] → [[1,2,3,4,5]] [5,1] → [[1],[2],[3],[4],[5]] [6,3] → [[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,3,4],[1,3,5],[1,3,6],[1,4,5],[1,4,6],[1,5,6],[2,3,4],[2,3,5],[2,3,6],[2,4,5],[2,4,6],[2,5,6],[3,4,5],[3,4,6],[3,5,6],[4,5,6]]
Java · 解法代码class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> res = new ArrayList<>(); dfs(n, k, 1, new ArrayList<>(), res); return res; } private void dfs(int n, int k, int start, List<Integer> path, List<List<Integer>> res) { int need = k - path.size(); // 还需要再选几个数 if (need == 0) { res.add(new ArrayList<>(path)); return; } for (int i = start; i <= n - need + 1; i++) { // 剪枝：i 之后（含 i）至少还要剩下 need 个数 path.add(i); dfs(n, k, i + 1, path, res); // 只往后选，保证组合里数字递增 path.remove(path.size() - 1); } } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [4,2] → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] [1,1] → [[1]] [5,3] → [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]] [5,5] → [[1,2,3,4,5]] [5,1] → [[1],[2],[3],[4],[5]] [6,3] → [[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,3,4],[1,3,5],[1,3,6],[1,4,5],[1,4,6],[1,5,6],[2,3,4],[2,3,5],[2,3,6],[2,4,5],[2,4,6],[2,5,6],[3,4,5],[3,4,6],[3,5,6],[4,5,6]]
Go · 解法代码func combine(n int, k int) [][]int { res := [][]int{} path := []int{} var dfs func(start int) dfs = func(start int) { need := k - len(path) // 还需要再选几个数 if need == 0 { res = append(res, append([]int{}, path...)) return } for i := start; i <= n-need+1; i++ { // 剪枝：i 之后（含 i）至少还要剩下 need 个数 path = append(path, i) dfs(i + 1) // 只往后选，保证组合里数字递增 path = path[:len(path)-1] } } dfs(1) return res }
$ go build -o bin . && ./bin < cases.jsonl [4,2] → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] [1,1] → [[1]] [5,3] → [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]] [5,5] → [[1,2,3,4,5]] [5,1] → [[1],[2],[3],[4],[5]] [6,3] → [[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,3,4],[1,3,5],[1,3,6],[1,4,5],[1,4,6],[1,5,6],[2,3,4],[2,3,5],[2,3,6],[2,4,5],[2,4,6],[2,5,6],[3,4,5],[3,4,6],[3,5,6],[4,5,6]]
JavaScript · 解法代码function combine(n, k) { const res = []; const path = []; const dfs = (start) => { const need = k - path.length; // 还需要再选几个数 if (need === 0) { res.push([...path]); return; } for (let i = start; i <= n - need + 1; i++) { // 剪枝：i 之后（含 i）至少还要剩下 need 个数 path.push(i); dfs(i + 1); // 只往后选，保证组合里数字递增 path.pop(); } }; dfs(1); return res; }
$ node run.js < cases.jsonl [4,2] → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] [1,1] → [[1]] [5,3] → [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]] [5,5] → [[1,2,3,4,5]] [5,1] → [[1],[2],[3],[4],[5]] [6,3] → [[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,3,4],[1,3,5],[1,3,6],[1,4,5],[1,4,6],[1,5,6],[2,3,4],[2,3,5],[2,3,6],[2,4,5],[2,4,6],[2,5,6],[3,4,5],[3,4,6],[3,5,6],[4,5,6]]
C++ · 解法代码#include <vector> using namespace std; class Solution { void dfs(int n, int k, int start, vector<int>& path, vector<vector<int>>& res) { int need = k - (int)path.size(); // 还需要再选几个数 if (need == 0) { res.push_back(path); return; } for (int i = start; i <= n - need + 1; i++) { // 剪枝：i 之后（含 i）至少还要剩下 need 个数 path.push_back(i); dfs(n, k, i + 1, path, res); // 只往后选，保证组合里数字递增 path.pop_back(); } } public: vector<vector<int>> combine(int n, int k) { vector<vector<int>> res; vector<int> path; dfs(n, k, 1, path, res); return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [4,2] → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] [1,1] → [[1]] [5,3] → [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]] [5,5] → [[1,2,3,4,5]] [5,1] → [[1],[2],[3],[4],[5]] [6,3] → [[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,3,4],[1,3,5],[1,3,6],[1,4,5],[1,4,6],[1,5,6],[2,3,4],[2,3,5],[2,3,6],[2,4,5],[2,4,6],[2,5,6],[3,4,5],[3,4,6],[3,5,6],[4,5,6]]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
k 取 n 的一半，n 分别为 10、14、16、18，每个规模取三次中最快的一次，基准是 itertools.combinations：
n（k = n // 2） | 暴力解 | 本文解法
10 | 0.021 ms | 0.054 ms
14 | 0.415 ms | 0.866 ms
16 | 1.963 ms | 3.296 ms
18 | 26.762 ms | 14.443 msn = 18、k = 9 时有 48620 个组合。这里手写回溯（14.4ms）比 itertools.combinations（26.8ms）更快，这有点出乎我的预期，因为基准还要把每个元组转成列表；n 更小时基准更快（n = 14 时 0.415ms 对 0.866ms）。我没有深究这个转折的原因，可能与基准一次性生成了全部元组再转换的内存开销有关，这只是猜测。两者的耗时都随 C(n, k) 快速增长。
Python 版本另外和 itertools.combinations 做了随机对拍，n 取 1 到 9，k 取 1 到 n：
随机对拍 500 组（n 取 1 到 9，k 取 1 到 n（结果按集合比较）），solve 与 brute 的结果全部一致。
n 只有很少的取值，固定用例和对拍合起来覆盖了大部分。另外四种语言只在上面 12 组固定用例上验证过。
下面的演示用 n = 4，k = 2，共 6 个组合。观察：选了 1 之后还需要 1 个，下一个从 2 起选；当选到 4 作为第一个数时，剩下没有数可选了，所以第一层的循环只试到 3（n - need + 1 = 4 - 2 + 1 = 3）。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的组合集合与 solve 的返回值一致。