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], ]
比较显然的dfs，不过同样是dfs，由于对递归条件以及递归进入的方法不同导致差异很大。 最开始写的方法排名0.2%，是使用visit数组。 仔细想想就会发现visit数组是没有必要的，其大小完全可以由i的遍历范围来进行控制。
所以dfs问题还是需要多思考而非直接模拟~
故DFS有一个非常重要的，避免直接使用visit数组的方法 可以归纳为一个模板
void dfs(T temp,vector< T> result,int start ){ if(到达了边界条件){ temp加入result； return; } //重点在这里 for(int i=**start**;i< n;i++){ //进行DFS（意思即改变一个状态-> 递归 -> 回滚状态） //注意这里递归的时候，开始状态为i+1【因为循环是处理到第i位，之后要从i+1位开始】 } } class Solution { public: int number,n; vector<vector<int>> combine(int n, int k) { this->n=n; this->number=k; vector<vector<int> > result; vector<int> temp; //由于是从前往后，可以通过控制递归条件达到不重复遍历，故不需要标记数组 // vector<bool> visit(n,false); // visit[i]=true; // visit[i]=false; generate(temp,1,0,result); return result; } void generate(vector<int>& temp,int start,int size,vector<vector<int> >& result){ if(size==this->number){ result.push_back(temp); return; } //应当从start开始而非size开始 //因为size可能不选，停留在0，导致后面仍然需要一个判断 // if(!size || (size && temp[size-1]<i+1) ){ //所以可以在dfs的时候，传入i+1作为下一个的start，保证下一个数始终比当前数大 for(int i=start;i<=n;i++){ temp.push_back(i); generate(temp,i+1,size+1,result); temp.pop_back(); } } };