一天一道LeetCode
本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github
欢迎大家关注我的新浪微博，我的新浪微博
欢迎转载，转载请注明出处
（一）题目
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],
]
（二）解题
本题大意：给定两个整形数，ｎ和ｋ，从１～ｎ中找出所有ｋ个数的组合。
这题是典型的回溯问题。分析一下当ｎ＝４，ｋ＝3的情况：
维持一个vector变量，当它的长度小于3时，按顺序往里面放数字。
第一个满足长度等于3的组合为1，2，3，接下来回溯弹出3，继续放数字4
第二个满足长度等于3的组合为1，2，4，然后回溯弹出4，没有数字放了，就继续回溯弹出2，再放入3和4
第三个满足长度等于3的组合为1，3，4，然后回溯弹出3，4和1，放入2，3，4
第四个满足长度等于3的组合为2，3，4。至此，算法结束。
class Solution {
public:
vector<vector<int>> ret;
vector<vector<int>> combine(int n, int k) {
vector<int> temp;
dfscombine(n,1,k,temp);
return ret;
}
void dfscombine(int n,int start,int k,vector<int> & temp)
{
if(temp.size()==k){//当长度为k时，将结果存在ret中
ret.push_back(temp);
return;
}
for(int i = start ; i <= n ; i++)
{
temp.push_back(i);//放入数字
dfscombine(n,i+1,k,temp);
temp.pop_back();//回溯到上一步
}
}
};