【递归，搜索与回溯算法】穷举 vs 暴搜 vs 深搜 vs 回溯 vs 剪枝算法入门专题详解
前言
什么是回溯算法？
- 回溯算法是一种经典的递归算法，通常用于解决组合问题、排列问题和搜索问题等。
回溯算法的基本思想
- 从一个初始状态开始，按照一定的规则向前搜索，当搜索到某个状态无法前进时，回退到前一个状态，再按照其他的规则搜索。
- 回溯算法在搜索过程中维护一个状态树，通过遍历状态树来实现对所有可能解的搜索。
回溯算法的核心思想
- “试错”，即在搜索过程中不断地做出选择，如果选择正确，则继续向前搜索；
- 否则，回退到上一个状态，重新做出选择。
- 回溯算法通常用于解决具有多个解，且每个解都需要搜索才能找到的问题。
回溯算法的应用
总结
- 回溯算法是一种非常重要的算法，可以解决许多组合问题、排列问题和搜索问题等。回溯算法的核心思想是搜索状态树，通过遍历状态树来实现对所有可能解的搜索。
- 回溯算法的模板非常简单，但是实现起来需要注意一些细节，比如如何做出选择、如何撤销选择等。
全排列
1. 题目解析
2. 算法原理
解法 一 : 暴力枚举
我们可以定义三层 for 循环，来解决这道问题；但是如果要枚举的数数量非常大呢？我们肯定不可能嵌套太多层循环；
解法二：递归
像这种穷举的题目，使用暴力枚举是非常麻烦的，此时，我们可以使用递归；不同回溯的题使用模板是有出入的，我们做这类递归回溯的题，最重要弄清楚背后的原理，要能够清楚地画出决策树，很多时候模板会限制我们的思维；
2.1 决策树
2.1.1 决策树的定义
2.1.2 画出决策树 
把每一步的决策画出来，我们就可以实现不重不漏地枚举出所有的情况，最开始的节点表示刚开始的位置枚举的所有节点；
2.2 全局变量
2.2.1 全局变量的定义方法
需要一个全局变量的 List<List<Integer>> ，来记录我们的最终结果；
两种方法都能起到记录的效果，但是最好还是在方法外单独定义出来这个全局变量；只需要在方法中重新实例化全局变量即可
2.2.2 定义全局变量
2.3 dfs() 函数
仅需关心某一个节点在做什么：
2.4 处理细节问题
2.4.1 递归出口
在决策树中，我们不需要遍历被剪枝的节点所在的路径，所以在遍历到决策树的叶子节点时，直接添加结果即可；如果 path.size() == nums.length，说明已经遍历该路径所有节点，类似 root==null；
那可以在返回之前，add 之后，先恢复现场吗？可以，但是没必要；我们可以回溯到上一层之后，再统一进行恢复现场；
2.4.2 剪枝
我们对决策树的一层剪枝进行分析，通过分析设置出剪枝对应的操作
定义全局变量 check 数组
boolean 数组的作用：标记在某一条路径上，当前遍历的数对应的nums的下标的使用情况；
boolean 元素记录的是 nums 数组对应的下标，而不是下标对应的元素，如果在递归到下一个数，发现这个数对应 check 的元素是 true，则说明当前遍历元素是重复元素，也因此无法进入判断条件：
2.4.3 回溯
当递归到决策树的最后一层，需要把 path 回溯给上一层，此时需要恢复现场用于其他分支的递归，所以需要去掉最后一个元素；
因为 check 数组也是全局变量，所以我们需要对 path 和 check 同时进行恢复现场；
2.5 总结
3. 编写代码
子集
题目解析
算法原理
解法一：固定一个元素，枚举下一个元素选或不选
决策树
全局变量
设计函数结构
根据这个决策树，我们设计出函数头 dfs( nums , i )
解法二：根据子集的元素个数，枚举所有子集
决策树
注意：决策树执行添加元素的操作前，要先从子集末尾元素来判断是否可以添加；如 [1 , 2 ] 子集，可以添加子集个数为 [ 1 , 2 , 3 ]，如果是 [ 2 , 3 ] ，[ 3 ] 这样的子集，则不能继续添加元素；
全局变量
设计函数结构
从两棵树的节点个数来看，第二棵决策树是优于第一棵决策树的；
编写代码
解法一：
解法二：
