回溯模板如下：

void backtracking(参数){
    if(终止条件){
        存放结果；
        return；
    }

    for(选择: 本层集合中元素(树中结点孩子的数量就是集合的大小)){
        处理结点；
        backtracking(路径，选择列表);   // 递归
        回溯，撤销处理结果
    }
}

把组合问题想象为如下树形结构

每次从集合元素中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
图中n相当于树的宽度，k相当于树的深度。每次搜索到叶子结点，我们就得到了一个结果。只需要把达到叶子结点的结果收集起来，就可以求得n个数中k个数的组合集合。

回溯三步曲

• 递归函数的返回值以及参数
  参数除了必须的n和k外，还需要一个startIndex，这个参数用来记录本层递归中，集合从哪里开始遍历（集合为[1,…,n]）
  每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就得靠startIndex。
  

vector<vector<int>> result;//用来存放结果
vector<int> path; //用来存放符合条件的单一结果
// 即函数为:
void backtracking(int n, int k, int startIndex)

• 回溯终止条件
  什么时候到达所谓的 叶子结点了呢？
  path数组的大小如果达到k，说明找到了一个子集大小为k的集合了，在图中path存的即为根节点到叶子结点的路径。
  用result二维数组，把path保存起来，并终止本层递归。
  故终止条件为：

if(path.size()==k){
	result.push_back(path);
	return;
}

• 单层搜索的过程
  回溯法的搜索过程，就是遍历整颗树的过程，从图中可以看出，用for循环进行横向遍历，用递归进行纵向遍历。
  以此遍历完整棵树。

backtracking(n, k, i + 1); //递归控制树的纵向遍历
//i+1就保证了下次的选择是基于本次的

for(int i = startIndex; i <= n; i++){//控制树的横向遍历
	path.push_back(i); //处理结点
	backtracking(n, k, i + 1); //递归控制树的纵向遍历
	path.pop_back();//回溯，撤销处理的结点
}

此处可以进行减枝优化：

i <= n - (k - path.size()) + 1
已经选择的元素: path.size()
还需要选择的元素: k - path.size()
在集合n中至多要从该起点位置: n - (k - path.size()) + 1，开始遍历

for(int i = startIndex; i <= n - (k - path.size()) + 1; i++){//控制树的横向遍历
	path.push_back(i); //处理结点
	backtracking(n, k, i + 1); //递归控制树的纵向遍历
	path.pop_back();//回溯，撤销处理的结点
}

组合整段代码如下：

class Solution {
private:
    vector<vector<int>> res;

    //求解C(n, k)，当前已经找到的组合存储在c中，需要从start开始搜索新的元素
    void generateCombinations(int n, int k, int start, vector<int> &p){
        if(p.size() == k){
            res.push_back(p);
            /*for(int i = 0; i < p.size(); i++)
                cout<<p[i];
            cout<<endl;
            cout<<"complete: return1"<<endl;*/
            return;
        }
        for(int i = start; i <= n ; i++){ //i = start
            p.push_back(i);
            generateCombinations(n, k, i+1, p); // i+1就保证了下次的选择是基于本次的
            p.pop_back(); //!

            //cout<<"return2"<<endl;

        }

        //cout<<"complete: return3"<<endl;
        return;
    }
public:
    vector<vector<int>> combine(int n, int k) {
        if(n <= 0 || k <= 0 || k > n){
            return res;
        }
        vector<int> p;
        generateCombinations(n, k, 1, p);

        return res;
    }
};