[LeetCode]77. Combinations

Question

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

Input: n = 4, k = 2

Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

Solution

问题解析

题目给定n,k表示从[1,n]n个数中选择k个数构成一个组合,现在求所有可能的组合情况。

比如例子中,n=4, k=2,表示从1,2,3,4几个数中选2个数构成一个组合,求所有的组合情况。

因为是组合,[1,2]和[2,1]表示一种情况,我们只取一种[1,2]也就是说构成组合的数组是一个增序的。采用递归方法,dfs深度优先遍历(回溯法)。

Version One

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
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
if (k > n || k < 0 || n < 0) return {};//有效性判断
vector<vector<int>> res;
vector<int> temp;
if (n < k) return res;
helper(n, k, res, temp, 1);

return res;
}
private:
void helper(int n, int k, vector<vector<int>>& res, vector<int>& temp, int begin){//使用应用传参,更节省空间
if (temp.size() == k){//满足k个数
res.push_back(temp);
return;
}
for (int i=begin; i<=n; i++){
temp.push_back(i);
helper(n, k, res, temp, i+1);
// 后续数必须大于前面的数:因为[1,2]和[2,1]是一种情况
temp.pop_back();//回溯 or dfs
}
}
};

Version Two

上面方法可以做优化,比如1,2,3,4,k=2,当第一次4时,之后没有元素,一定不满足情况。我们可以事先做一个判断,通过计算比当前元素大的元素个数和还需要的元素个数做比较,如果小,不进行递归。这就是做剪枝处理。

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
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
if (k > n || k < 0 || n < 0) return {};
vector<vector<int>> res;
vector<int> temp;
if (n < k) return res;
helper(n, k, res, temp, 1);

return res;
}
private:
void helper(int n, int k, vector<vector<int>>& res, vector<int>& temp, int begin){
if (temp.size() == k){
res.push_back(temp);
return;
}
// 剪枝--当前temp数组还需要k-temp.size()个元素;
// 所以在[i, n]至少要有k-temp.size()个元素
// 比如,n=4,k=2,i = 4, temp = []时, k-temp.size() = 2,还需要两个元素,这时候[i, n]元素个数为1,不可能有解
// 所以,i的变化是有一个更细的边界(比n更细),i的右边界是:n - (k-temp.size()) + 1; 最远移动到n-(k-temp.size())+1,更远的话一定没有解。
// i = 4 ;n-(k-temp.size()) + 1 =3; 不进行循环
// n --> n - (k-temp.size()) + 1;
for (int i=begin; i<=n - (k-temp.size()) + 1; i++){
temp.push_back(i);
helper(n, k, res, temp, i+1);
// 后续数必须大于前面的数:因为[1,2]和[2,1]是一种情况
temp.pop_back();//回溯 or dfs
}
}
};

Version Three: C(n, k) = C(n-1, k-1) + C(n-1, k)

利用组合数的一个定理: C(n, k) = C(n-1, k-1) + C(n-1, k). 语言描述:求从n个数里取k个数的组合数,我们已n为考虑对象,根据k个数里有没有取n可以分为两种情况:

  1. 取n:然后在n-1个数里再选k-1个数
  2. 不取n:然后在n-1个数里选k个数

所以,n个数里选k个的组合数是两种情况的和。

根据这个定理。举例来说,n=3,k=2;

C(n-1, k-1) = C(2, 1) = [1] [2]

C(n-1, k) = C(2, 2) = [1, 2]

而C(3,2) = [1, 2] [1, 3] [2, 3]

观察可以看出来C(n-1, k-1)比要求少一个数n,我们把n依次添加到k-1的组合里,最终和另一种情况合并就可以得到最终解。

So,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<vector<int>> combine(int n, int k) {

if (k > n || k < 0) return {};//有效性判断
if (k == 0) return {{}};//递归终止条件
// Solution 2: C(n, k) = C(n-1, k) + C(n-1, k-1)
// 语言描述:n中取k的组合数等于:取n情况下在剩余n-1取k-1个数的组合数
// 加上 不取n情况下,在剩余n-1个数的情况下取k个数的组合数
vector<vector<int>> res = combine(n-1, k-1);
for (auto &a : res) a.push_back(n);
for (auto &a : combine(n-1, k)) res.push_back(a);

return res;
}
};

References

https://www.cnblogs.com/grandyang/p/4332522.html https://blog.csdn.net/wys2011101169/article/details/72887512 https://blog.csdn.net/u010500263/article/details/18435495

您的支持就是我更新的最大动力!谢谢!