6.10回溯专题day1组合问题（77. 组合）

class Solution {
public:
    vector path;
    vector> ans;
    vector> combine(int n, int k) {
        backtracking(n, k, 1);
        return ans;
    }

    void backtracking(int n, int k, int startindex){
        if(path.size() == k){
            ans.push_back(path);
            return;
        }

        for(int i = startindex; i<=n; i++){
            path.push_back(i);
            backtracking(n, k, i+1);
            path.pop_back();
        }
    }
};

还有一种优化方法
所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。可以仔细理解一下

class Solution {
public:
    vector path;
    vector> ans;
    vector> combine(int n, int k) {
        backtracking(n, k, 1);
        return ans;
    }

    void backtracking(int n, int k, int startindex){
        if(path.size() == k){
            ans.push_back(path);
            return;
        }

        for(int i = startindex; i<=n-(k-path.size())+1; i++){
            path.push_back(i);
            backtracking(n, k, i+1);
            path.pop_back();
        }
    }
};

这块可以理解下n-(k-path.size())+1这里，假设n=4,k=3.可以把这个理解为从哪里开始搜索。如果搜索到，path中有2，那么就要从4-(3-1)+1=3开始搜索都比较合理。