leetcode 77 组合 C/C++ 深度优先搜索

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
void recursive(int n,int k,int value, int index,vector<int> &com_case, vector<vector<int>> &allcases){
if(index < k) //当还没有到第K个数时
{
com_case.push_back(value);
recursive(n,k,value+1,index+1,com_case,allcases);
//当前组合这个位置放这个数时，其他可能的组合已经列举完毕了，尝试列举这个位置不放这个数的情况
for(int i = value + 1; i <= n-k+index; i++){
com_case.pop_back();
com_case.push_back(i);
recursive(n,k,i+1,index+1,com_case,allcases);
}
com_case.pop_back();
}else{ // 如果已经到了第K个数
com_case.push_back(value);
allcases.push_back(com_case);
com_case.pop_back();
for(int i = value + 1;i<=n;i++) // 列举这一个位置其他数的情况
{
com_case.push_back(i);
allcases.push_back(com_case);
com_case.pop_back();
}
}
}

vector<vector<int>> combine(int n, int k) {
vector<int> com_case;
vector<vector<int>> allcases;
recursive(n,k,1,1,com_case,allcases);
return allcases;
}
};

int main(){
Solution s;
vector<vector<int>> retVec = s.combine(4,3);
for(auto it = retVec.begin();it!=retVec.end();it++)
{
for(auto ij = (*it).begin(); ij!=(*it).end();ij++) cout<<*ij<<" ";

cout<<endl;
}
cout<<endl;
return 1;
}