77.Combinations
77.Combinations
难度:Medium
给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
示例:
1
输入: n = 4, k = 2
2
输出:
3
[
4
[2,4],
5
[3,4],
6
[2,3],
7
[1,2],
8
[1,3],
9
[1,4],
10
]
Copied!
可以采用递归的方法,n个数里找k个数,可以分两类,第一类有n,第二类没有。 第一类可以看做是n-1个数里找k-1个数。 第二类可以看做是n-1个数里找k个数。 以此方式进行递归。 注意判断特殊情况。
1
class Solution {
2
3
public:
4
vector<vector<int>> combine(int n, int k) {
5
// cout<<n<<" "<<k<<endl;
6
if(n<k)
7
{
8
vector<vector<int>>res;
9
return res;
10
}
11
if(n==k) {
12
vector<int >tmp;
13
for(int i=1;i<=n;i++)
14
tmp.push_back(i);
15
vector<vector<int>>res;
16
res.push_back(tmp);
17
return res;
18
}
19
if(k==1)
20
{
21
vector<vector<int>> res;
22
for(int i=1;i<=n;i++)
23
{
24
vector<int>tmp(1,i);
25
res.push_back(tmp);
26
}
27
return res;
28
}
29
30
vector<vector<int>> res1= combine(n-1, k);
31
vector<vector<int>>res2= combine(n-1, k-1);
32
for(auto v: res2)
33
{
34
v.push_back(n);
35
res1.push_back(v);
36
}
37
38
39
return res1;
40
}
41
};
Copied!
执行用时 :164 ms, 在所有 C++ 提交中击败了46.10%的用户 内存消耗 :54.7 MB, 在所有 C++ 提交中击败了22.81%的用户
Copy link