组合
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任意顺序 返回答案。
示例 1
示例 2
模拟答题者思考
1. 我先想暴力：从 1..n 中任意选 k 个数的所有子集，检查大小是否为 k——思路对，但子集有 2^n 个，n=20 会爆。
2. 重复在哪里？组合不关心顺序，[1,2] 与 [2,1] 是同一答案；若每层从 1 重新选，会大量生成排列等价物。
3. 关键转化：维护 start，每层只从 start..n 选，且递归传 i+1，使 path 内数字严格递增，自然去重；len(path)==k 时收集。
4. 剪枝：还需选 need = k - len(path) 个数时，若 n - i + 1 < need，后面数字不够凑满，可直接 break。例 n=4,k=2：第一层 i 只需到 3，因为以 4 开头只剩一个数。
5. 边界 n=1,k=1 直接 [[1]]；n≤20、答案规模可控，回溯 + 剪枝足够。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
path | list<int> | 定义：当前已选数字组成的组合（升序片段） 维护：DFS 每层在末尾追加一个比上一数更大的整数，回溯时 pop 撤销更新：尝试数字 i 时 append(i)；该分支探索完毕后 pop |
start | int | 定义：本轮可选数字的下界（含自身），候选来自 [start, n]维护：只从 start 往后选，保证组合内严格递增，避免 [1,2] 与 [2,1] 重复更新：选了 i 后下一层传 start = i + 1 |
need | int | 定义：距离凑满 k 个数还差几个（k - len(path)）维护：每追加一个数 need 减 1；为 0 时当前 path 即合法组合更新：循环上界剪枝：若从 i 到 n 剩余可选数不足 need 则 break |
ans | list<list<int>> | 定义：所有长度为 k 的组合维护：仅当 len(path) == k 时将 path 的副本加入更新：每到达叶子层追加一次；中途不收集半成品 |
落码步骤
1. 初始化结果 ans 与当前路径 path
2. 定义 DFS backtrack(start)：若 len(path) == k，将 path[:] 加入 ans 并返回
3. 计算 need = k - len(path)，对 i 从 start 到 n：若 n - i + 1 < need 则 break（剩余数字不够）
4. 将 i 追加到 path，递归 backtrack(i + 1)
5. 回溯：从 path 弹出末尾元素，继续尝试下一个 i
6. 从 backtrack(1) 启动，返回 ans
代码实现
class Solution:
def combine(self, n: int, k: int) -> list[list[int]]:
ans: list[list[int]] = []
path: list[int] = []
def backtrack(start: int) -> None:
if len(path) == k:
ans.append(path[:])
return
need = k - len(path)
for i in range(start, n + 1):
if n - i + 1 < need:
break
path.append(i)
backtrack(i + 1)
path.pop()
backtrack(1)
return ansclass Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> ans;
vector<int> path;
function<void(int)> dfs = [&](int start) {
if ((int)path.size() == k) {
ans.push_back(path);
return;
}
int need = k - (int)path.size();
for (int i = start; i <= n; i++) {
if (n - i + 1 < need) break;
path.push_back(i);
dfs(i + 1);
path.pop_back();
}
};
dfs(1);
return ans;
}
};
// 时间 O(k·C(n,k))，空间 O(k) 递归栈复杂度分析
O(k · C(n,k))（共 C(n,k) 组组合，每组拷贝长度 k）
O(k)（递归栈深度，不计输出）
常见坑
把组合当排列：每层必须从 start 往后选并传 i+1，不能每层都从 1 枚举，否则会重复且漏剪枝意义。
收集答案未拷贝 path：应 ans.append(path[:]) 或在 C++ 于 size==k 时 push 当前 path 副本，否则回溯修改会污染结果。
忘记数量剪枝：不判断 n - i + 1 < need 仍能通过，但在 n 较大时会多搜无效分支。
必测边界 Case
n = 4, k = 4 → [[1,2,3,4]]（只能全选）
n = 4, k = 1 → [[1],[2],[3],[4]]
n = 1, k = 1 → [[1]]
n = 4, k = 2 → 共 6 组，顺序任意
第一层在 n=4,k=2 时 i 最大为 3；以 4 开头无法凑满两个数