0077. 组合【中等】
1. 📝 题目描述
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按任何顺序返回答案。
示例 1:
输入:n = 4, k = 2
输出:
[
[2, 4], [3, 4], [2, 3],
[1, 2], [1, 3], [1, 4],
]1
2
3
4
5
6
2
3
4
5
6
示例 2:
输入:n = 1, k = 1
输出:[[1]]1
2
2
提示:
1 <= n <= 201 <= k <= n
2. 🎯 s.1 - 回溯 + 剪枝
c
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** answers;
int answerSize;
int limitN;
int targetK;
int path[20];
int pathSize;
int getCombinationCount(int n, int k) {
if (k > n - k) k = n - k;
long long count = 1;
for (int i = 1; i <= k; i++) {
count = count * (n - k + i) / i;
}
return (int)count;
}
void backtrack(int start, int* returnColumnSizes) {
if (pathSize == targetK) {
int* combination = (int*)malloc(targetK * sizeof(int));
for (int i = 0; i < targetK; i++) combination[i] = path[i];
answers[answerSize] = combination;
returnColumnSizes[answerSize] = targetK;
answerSize++;
return;
}
for (int num = start; num <= limitN - (targetK - pathSize) + 1; num++) {
path[pathSize++] = num;
backtrack(num + 1, returnColumnSizes);
pathSize--;
}
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
int total = getCombinationCount(n, k);
answers = (int**)malloc(total * sizeof(int*));
*returnColumnSizes = (int*)malloc(total * sizeof(int));
answerSize = 0;
limitN = n;
targetK = k;
pathSize = 0;
backtrack(1, *returnColumnSizes);
*returnSize = answerSize;
return answers;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
js
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function (n, k) {
const ans = []
const path = []
const backtrack = (start) => {
if (path.length === k) {
ans.push([...path])
return
}
for (let num = start; num <= n - (k - path.length) + 1; num++) {
path.push(num)
backtrack(num + 1)
path.pop()
}
}
backtrack(1)
return ans
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
py
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
for num in range(start, n - (k - len(path)) + 2):
path.append(num)
backtrack(num + 1)
path.pop()
backtrack(1)
return ans1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
- 时间复杂度:
,一共需要生成 个长度为 的组合,每次加入答案都要复制当前路径 - 空间复杂度:
,递归栈深度和当前路径长度都不会超过 ;若计入返回结果,总空间为
算法思路:
- 用
path记录当前已经选出的组合,用start表示下一次只能从哪个数字开始选,保证组合中的元素严格递增,从而避免重复 - 每次从区间
[start, n]中挑一个数字加入path,然后递归去选择下一个数字 - 当
path的长度等于k时,说明已经构造出一个合法组合,将其拷贝加入答案
2.1. 剪枝策略
path.length 表示当前已经固定的数字的数量,还差 x 个数字凑满 k 个数,x = k - path.length。
如果当前枚举的起点太靠后,后面剩余数字数量(小于 x)不足以凑满长度为 k 的组合,就没有继续搜索的必要。
边界区间:
[n - x + 1, n]=> 这段区间的数字全算上,一共x个数字,正好可以让path.length凑满k个数[n - x + 2, n]=> 这段区间的数字全算上,一共x - 1个数字
综上:循环上界可以写成 n - (k - path.length) + 1(可以取到)。
这种剪枝不会改变结果,只是提前跳过不可能得到合法组合的分支,提高搜索效率。