代码随想录算法训练营第24天（回溯算法01 |● 理论基础 ● 77. 组合

理论基础

其实在讲解二叉树的时候，就给大家介绍过回溯，这次正式开启回溯算法，大家可以先看视频，对回溯算法有一个整体的了解。
文章讲解：理论基础
视频讲解：理论基础

理解

虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢？因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。
回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）

回溯法解决的问题

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

回溯三部曲

1. 回溯函数模板返回值及参数
2. 回溯函数终止条件
3. 回溯搜索的遍历过程
   for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历

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

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

77. 组合

对着 在 回溯算法理论基础 给出的 代码模板，来做本题组合问题，大家就会发现 写回溯算法套路。
在回溯算法解决实际问题的过程中，大家会有各种疑问，先看视频介绍，基本可以解决大家的疑惑。
本题关于剪枝操作是大家要理解的重点，因为后面很多回溯算法解决的题目，都是这个剪枝套路。
题目链接/文章讲解：77. 组合
视频讲解：77. 组合
剪枝操作：剪枝操作

解题思路

如果解决一个问题有多个步骤，每一个步骤有多种方法，题目又要我们找出所有的方法，可以使用回溯算法；
对于这一类问题，画图帮助分析是非常重要的解题方法。
回溯三部曲

1. 递归函数的返回值以及参数

• 两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
• int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历。

2. 回溯函数终止条件
   什么时候到达所谓的叶子节点了呢？
   path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了。此时用result二维数组，把path保存起来，并终止本层递归。
3. 单层搜索的过程
   for循环用来横向遍历，递归的过程是纵向遍历。

剪枝优化

可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
优化过程如下：

1. 已经选择的元素个数：path.size();
2. 还需要的元素个数为: k - path.size();
3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
4. 为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
   举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。从2开始搜索都是合理的，可以是组合[2, 3, 4]。

注意

如果对于回溯算法还理解不太透彻的朋友，可以在递归方法的前后，把 path 变量打印出来看一下

for(int i = startInddex; i <= n - (k - path.size()) + 1; i++){  // 控制树的横向遍历，注意下一层搜索要从i+1开始
            path.add(i);             // 处理节点 
            System.out.println("递归之前 => " + path);
            backtracking(n, k, i+1); // 递归：控制树的纵向遍历
            path.removeLast();       // 回溯，撤销处理的节点
            System.out.println("递归之前 => " + path);
        }

// 回溯 未剪枝
class Solution {
    List<List<Integer>> result = new ArrayList<>();  // 用来存放符合条件的集合
    LinkedList<Integer> path = new LinkedList<>();   // 用来存放符合条件的结果
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
    public void backtracking(int n, int k, int startInddex){
        if(path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = startInddex; i <= n; i++){  // 控制树的横向遍历，注意下一层搜索要从i+1开始
            path.add(i);             // 处理节点 
            backtracking(n, k, i+1); // 递归：控制树的纵向遍历
            path.removeLast();       // 回溯，撤销处理的节点
        }
    }
}

// 回溯 剪枝版
class Solution {
    List<List<Integer>> result = new ArrayList<>();  // 用来存放符合条件的集合
    LinkedList<Integer> path = new LinkedList<>();   // 用来存放符合条件的结果
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
    public void backtracking(int n, int k, int startInddex){
        if(path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = startInddex; i <= n - (k - path.size()) + 1; i++){  // 控制树的横向遍历，注意下一层搜索要从i+1开始
            path.add(i);             // 处理节点 
            backtracking(n, k, i+1); // 递归：控制树的纵向遍历
            path.removeLast();       // 回溯，撤销处理的节点
        }
    }
}