Leetcode Index

77.Combinations

77.Combinations

难度:Medium

给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

可以采用递归的方法,n个数里找k个数,可以分两类,第一类有n,第二类没有。 第一类可以看做是n-1个数里找k-1个数。 第二类可以看做是n-1个数里找k个数。 以此方式进行递归。 注意判断特殊情况。

class Solution {
public:
vector<vector<int>> combine(int n, int k) {
// cout<<n<<" "<<k<<endl;
if(n<k)
{
vector<vector<int>>res;
return res;
}
if(n==k) {
vector<int >tmp;
for(int i=1;i<=n;i++)
tmp.push_back(i);
vector<vector<int>>res;
res.push_back(tmp);
return res;
}
if(k==1)
{
vector<vector<int>> res;
for(int i=1;i<=n;i++)
{
vector<int>tmp(1,i);
res.push_back(tmp);
}
return res;
}
vector<vector<int>> res1= combine(n-1, k);
vector<vector<int>>res2= combine(n-1, k-1);
for(auto v: res2)
{
v.push_back(n);
res1.push_back(v);
}
return res1;
}
};

执行用时 :164 ms, 在所有 C++ 提交中击败了46.10%的用户 内存消耗 :54.7 MB, 在所有 C++ 提交中击败了22.81%的用户