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%的用户
Last modified 11mo ago