77. 组合
题目描述
输入两个整数 n 和 k。
从 1 到 n 这些数里选出 k 个，不计顺序，就是一种组合。找出所有不同的组合并返回。
结果中各组合的先后顺序不限。
示例 1
输入：n = 4, k = 2 输出：[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
解释：从 1 到 4 中选 2 个，共 6 种。
示例 2
输入：n = 1, k = 1 输出：[[1]]
数据范围
1 <= n <= 201 <= k <= n
解题思路
组合按升序生成：dfs(start) 从 start 开始挑 path 的下一个数 x，然后从 x+1 继续。剪枝：还需要 k-len(path) 个数，所以 x 最大只能到 n-(k-len(path))+1，再大后面就凑不够了。path 长度达到 k 就记录。
为什么正确
path 严格递增，且剩余可选的数 [start, n] 至少还有 k-len(path) 个。
复杂度分析
时间 O(k · C(n,k))，空间 O(k)（不计输出）。
易错点
剪枝上界容易差一：是 n-(k-len(path))+1（含），写成 range 时右端要再加 1。另外记录时要复制 path，不能直接存引用。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res, path = [], []
def dfs(start):
if len(path) == k:
res.append(path[:])
return
for x in range(start, n - (k - len(path)) + 2):
path.append(x)
dfs(x + 1)
path.pop()
dfs(1)
return resclass Solution {
int n, k;
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
this.n = n;
this.k = k;
dfs(1);
return res;
}
void dfs(int start) {
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
for (int x = start; x < n - (k - path.size()) + 2; x++) {
path.add(x);
dfs(x + 1);
path.remove(path.size() - 1);
}
}
}class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> path;
function<void(int)> dfs = [&](int start) {
if ((int)path.size() == k) {
res.push_back(path);
return;
}
for (int x = start; x < n - (k - (int)path.size()) + 2; x++) {
path.push_back(x);
dfs(x + 1);
path.pop_back();
}
};
dfs(1);
return res;
}
};func combine(n int, k int) [][]int {
res, path := [][]int{}, []int{}
var dfs func(start int)
dfs = func(start int) {
if len(path) == k {
res = append(res, append([]int{}, path...))
return
}
for x := start; x < n-(k-len(path))+2; x++ {
path = append(path, x)
dfs(x + 1)
path = path[:len(path)-1]
}
}
dfs(1)
return res
}var combine = function(n, k) {
const res = [], path = [];
const dfs = (start) => {
if (path.length === k) {
res.push([...path]);
return;
}
for (let x = start; x < n - (k - path.length) + 2; x++) {
path.push(x);
dfs(x + 1);
path.pop();
}
};
dfs(1);
return res;
};function combine(n: number, k: number): number[][] {
const res: number[][] = [], path: number[] = [];
const dfs = (start: number): void => {
if (path.length === k) {
res.push([...path]);
return;
}
for (let x = start; x < n - (k - path.length) + 2; x++) {
path.push(x);
dfs(x + 1);
path.pop();
}
};
dfs(1);
return res;
}