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:
void DFS(int n,int k,vector<vector<int>> &result,vector<int> &path,int start)
{
if(path.size()==k)
{
result.push_back(path);
return;
}
for(int i=start;i<=n;i++) //从1开始算的，所有i到n
{
path.push_back(i);
DFS(n,k,result,path,i+1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
vector<int> path;
DFS(n,k,result,path,1);
return result;
}
};
