题解 | #组合#

class Solution {

public:

/**
 * 
 * @param n int整型 
 * @param k int整型 
 * @return int整型vector<vector<>>
 */
//用两种方式维护回溯状态。
vector<vector<int> > combine(int n, int k) {
    // write code here
     vector<int> vec;
    vector<vector<int> > sv;
    dfs(n,k,vec,sv,1,0);
    reverse(sv.begin(), sv.end());
    return sv;
}
void dfs(int n, int k,vector<int> vec,vector<vector<int> > &sv,int index,int count){
    if(count == k && index <= n+1){
        sv.push_back(vec);
        return;
    }
    else if(index == n+1) return;
    dfs(n,k,vec,sv,index+1,count);  //利用函数调用(局部参数的调用栈)来维持vec回溯状态
    vec.push_back(index);
    dfs(n,k,vec,sv,index+1,count+1);
}

//------------------------------------------------------------------------------------

vector<vector<int> > combine(int n, int k) {
    // write code here
    vector<vector<int>> res;
    vector<int> vec;
    backtrack(res, vec, n, k);
    return res;
}
void backtrack(vector<vector<int>> &res, vector<int> &vec,
        int n, int k) {
    if (vec.size() == k) { res.push_back(vec); return; }
    int start = vec.empty() ? 1 : vec[vec.size() - 1] + 1;
    for (int i = start; i <= n; ++i) {
        vec.push_back(i);
        backtrack(res, vec, n, k);
        vec.pop_back();        //利用vec本身push/pop过程 维持vec回溯状态
    }
}

};