LeetCode 77. 组合
题目描述
✅ 77. 组合
题意分析
从整数
1到n中选出恰好k个不同的数，返回所有可能的组合。组合只关心选中了哪些数，不关心选择顺序；同一组数换一个排列，仍然是同一个答案，不能重复收集。题目保证
1 <= k <= n，结果中的每组都必须含k个数，每个数只能使用一次。不同组合之间可以共享数字，答案的输出顺序不限。这里求的是全部组合，而不是某个组合、组合数量或元素和。
解法：回溯枚举组合
核心思路
[!blue]
每个组合都可以唯一地按从小到大排列。因此只生成严格递增的选择路径，就能让同一个组合只出现一次，也不会遗漏任何组合。选了当前数
num之后，后续只能从num + 1开始选，不需要再用集合判断重复。递归状态由当前路径
path和下一步允许选择的最小值start组成。路径保存已经选好的递增前缀；当前层依次尝试start及之后的数字，每选一个数，就递归决定剩余位置。递归返回后移除刚选的数，使下一个分支仍从相同前缀出发。枚举前还可以判断剩余数量是否足够。若还需要
need = k - path.size()个数，当前选择num后，还必须有至少need - 1个更大的数可选。可用数量是n - num，因此要求n - num >= need - 1，即num <= n - need + 1。超过这个上界的分支一定凑不满，直接不枚举即可。当路径长度达到
k，它就是一组完整答案。此时必须复制路径容器后加入结果：搜索过程还会删除和覆盖当前路径，结果需要保存这一刻的内容。Java 创建新列表，Go 将当前整数元素复制到新切片，随后结束这个分支。任何合法组合的递增排列，都能沿着它的各个数字依次走到一条搜索路径；数量剪枝也不会排除它，因为它确实还剩足够多的数字。所以递增选择保证不重复，完整枚举和安全剪枝保证不遗漏。
解题步骤
- 从空路径和
start = 1开始回溯。- 若路径已有
k个数，复制路径加入答案并返回。- 计算还需选择的数量
need，枚举num从start到n - need + 1。- 将
num加入路径，从num + 1递归；返回后移除路径末尾的num。- 所有分支完成后，返回收集到的全部组合。
代码实现
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> ans = new ArrayList<>();
backtrack(1, n, k, new ArrayList<>(), ans);
return ans;
}
private void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> ans) {
if (path.size() == k) {
// 保存路径快照，回溯对当前列表的修改不能影响答案。
ans.add(new ArrayList<>(path));
return;
}
// 当前数选完后，后面必须还够填满剩余位置。
int need = k - path.size();
for (int num = start; num <= n - need + 1; num++) {
path.add(num);
backtrack(num + 1, n, k, path, ans);
path.remove(path.size() - 1);
}
}
}
func combine(n int, k int) [][]int {
ans := make([][]int, 0)
path := make([]int, 0, k)
var dfs func(int)
dfs = func(start int) {
if len(path) == k {
// 保存路径快照，回溯对当前切片的修改不能影响答案。
ans = append(ans, append([]int(nil), path...))
return
}
// 当前数选完后，后面必须还够填满剩余位置。
need := k - len(path)
for num := start; num <= n-need+1; num++ {
path = append(path, num)
dfs(num + 1)
path = path[:len(path)-1]
}
}
dfs(1)
return ans
}
复杂度分析
- 时间复杂度：$O\left(k\binom{n}{k}\right)$。共有 $\binom{n}{k}$ 个组合，每个结果需要复制
k个元素；剪枝后的每个搜索前缀都能延伸为答案，搜索工作也不超过所有答案路径长度的总量级。- 空间复杂度：不计返回结果为 $O(k)$，用于当前路径和递归栈；结果本身占 $O\left(k\binom{n}{k}\right)$。
关键点总结
[!green]
- 固定每组的递增顺序，用搜索规则直接消除排列带来的重复。
start决定下一步能选谁，need决定当前数字最晚能选到哪里。- 保存答案时复制路径，尝试下一分支前撤销本次选择。
易错点总结
[!yellow]
- 下一层传
start + 1而非num + 1，会允许重新选择本层已经选过的数字，破坏递增性。- 收集结果时直接保存可变路径，后面的回溯修改会影响已有答案。
- 把剪枝上界固定为
n - k + 1，没有扣除已选数量，会在深层错误排除末尾数字。- 忘记撤销本次选择，会让后续分支带上上一分支的额外数字。
- 每个递归前缀都加入答案，会混入不足
k个数的选择；本题只收集长度恰好为k的路径。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 78. 子集 | 中等 | 原题枚举全部大小的子集，本题只收集恰好k个元素的选择。 |
| 216. 组合总和 III | 中等 | 同样固定组合大小，再额外限制元素和，可结合剩余数量与和的边界剪枝。 |
| 39. 组合总和 | 中等 | 在选择和撤销之间枚举组合；本题只约束选择数量，该题允许同一候选被多次选取。 |
| 40. 组合总和 II | 中等 | 在选择和撤销之间枚举组合；本题只约束选择数量，该题候选只能用一次且需去重。 |
| 90. 子集 II | 中等 | 在选择和撤销之间枚举组合；本题只约束选择数量，该题排序后跳过同层重复值。 |