1.回溯的本质：

• 回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
• 回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案

2.回溯法解决的问题：

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

3.回溯模板：

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

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

4.力扣77（组合问题）

        在回溯中，我们可以把递归和回溯的过程想象成一棵二叉树，每次取一位元素，且当path的长度为k时，那就说明我们遍历到了叶子节点的位置，我们就把结果入结果队列；在相等之前我们要递归遍历元素。下面用回溯三部曲解决问题：

• 递归函数的返回值以及参数：在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合

   LinkedList<Integer> path = new LinkedList<>();
   List<List<Integer>> res = new ArrayList(); 
   public void back(int n, int k,int startIndex) 

• 回溯函数终止条件：path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，path存的就是根节点到叶子节点的路径。

        if(path.size()==k){
            res.add(new ArrayList<>(path));
            return;
        }

• 单层搜索的过程：for循环每次从startIndex开始遍历，然后用path保存取到的节点i，然后递归遍历子集合，最后回溯弹出节点值。

//这里我们直接加上了剪枝操作，剪枝操作也就是对终止的条件进行收缩，除去不必要的递归遍历过程
        for(int i=startIndex;i<=n-(k-path.size())+1;i++){
            path.add(i);
            back(n,k,i+1);
            path.removeLast();
        }

整体代码：

   LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> res = new ArrayList();
    public List<List<Integer>> combine(int n, int k) {
        back(n,k,1);
        return res;
    }
    public void back(int n, int k,int startIndex) {
        if(path.size()==k){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=startIndex;i<=n-(k-path.size())+1;i++){
            path.add(i);
            back(n,k,i+1);
            path.removeLast();
        }
    }