思路：

用递归中嵌套for循环，抽象为n叉树，来取代暴力for循环。

储备：

代码随想录

问题重点：

1、

要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题。

递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。

回溯法解决的问题都可以抽象为树形结构（N叉树）

2、

可知很多都是等价的写法。要会区分。 

最后：

剪枝版：

class Solution {//剪枝版
public:

    vector<vector<int>> res;
    vector<int> path;

    void trace (int n,int k,int s) {

        if (k==path.size()) {//路径够长的话。这同时也是树的深度
            res.push_back(path);
            return ;
        }
        //当成n叉树.剩的连长度都不够就剪枝
        for (int i=s;i<=n-(k-path.size())+1;i++) {//左闭右闭，n-已有的=还需要的。再+1等于开始。因为要左闭
            path.push_back(i);
            trace(n,k,i+1);//传入每一次的新起点。是回溯的优化出来的东西也是目的
            path.pop_back();//全局回溯
        }
        return ;
    }

    vector<vector<int>> combine(int n, int k) {
        trace(n,k,1);
        return res;
    }
};

基础版：

class Solution {//基础版
public:

    vector<vector<int>> res;
    vector<int> path;

    void trace (int n,int k,int s) {

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

        for (int i=s;i<=n;i++) {
            path.push_back(i);
            trace(n,k,i+1);
            path.pop_back();
        }
        return ;
    }

    vector<vector<int>> combine(int n, int k) {
        trace(n,k,1);
        return res;
    }
};