首页 > 代码库 > Combinations
Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
class Solution {
public:
vector<vector<int> > combine(int n, int k)
{
vector<vector<int>> result;
if(k<=0) return result;
vector<int> v;
for(int i=0;i<k;i++) v.push_back(0);
for(int i=1;i<=n;i++)
{
v[0]=i;
get(result,v,n,k,1);
}
return result;
}
void get(vector<vector<int>>& result,vector<int>& v,int n,int k,int dep)
{
if(dep==k)
{
result.push_back(v);
return;
}
for(int i=v[dep-1]+1;i<=n;i++)
{
v[dep]=i;
get(result,v,n,k,dep+1);
}
}
};
public:
vector<vector<int> > combine(int n, int k)
{
vector<vector<int>> result;
if(k<=0) return result;
vector<int> v;
for(int i=0;i<k;i++) v.push_back(0);
for(int i=1;i<=n;i++)
{
v[0]=i;
get(result,v,n,k,1);
}
return result;
}
void get(vector<vector<int>>& result,vector<int>& v,int n,int k,int dep)
{
if(dep==k)
{
result.push_back(v);
return;
}
for(int i=v[dep-1]+1;i<=n;i++)
{
v[dep]=i;
get(result,v,n,k,dep+1);
}
}
};
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。