专题三：穷举vs暴搜vs深搜vs回溯vs剪枝（全排列）决策树与递归实现详解

题目分析：

给一个数组，列出它的全排列

算法原理分析：

这里就是一个穷举/枚举的原理，就是罗列所有的可能情况

第一步：画决策树（越详细越好）

就是你如何暴力穷举每一种情况，把你的思考过程详细的画下来

注意：决策树可能不一样，但如果决策树能写出代码，你的决策树就是对的，一道题可能有多种决策树

 

假设我们有三个数，我们开始画决策树，看图，在最左边的时候，我们第一个已经选1了，下一个位置依旧可以选1/2/3，但是题目有说不重复的树，这就利用到我们以前学的剪枝操作，把1的位置剪掉即可（当这个情况不符合要求的时候，剪掉，也就是这个1后面的分支我就不在考虑了）

 

可以自己尝试画一下决策树，看一下是否和上图一样 

可以发现我们每一个结点都是重复填1/2/3，无非就是有些要剪枝

每一个结点都在重复一件事，此时你是否想到递归，这样你的决策树就可以写成递归代码

第二步：设计代码

 考虑三点：1.全局变量

                   2.dfs函数

                   3.细节

1.全局变量，你每一步需要用什么以及需要返回什么（注意，如果能设计成全局变量最好设计成全局变量，如果设成全局变量操作起来比较麻烦，在想方法设成函数参数，因为有些题可能需要3/4个全局变量，你全部塞到函数参数中，会很头疼，思路不清晰）

这里我们发现：返回一个二维数组，所以我们可以设一个二维数组的全局变量ret去保存结果，最后返回即可

然后我们发现每次回溯->恢复现场也要一个全局变量，我们设一个path，path的作用：当你回溯的时候要恢复现场，也就是pop掉path的最后一个元素即可，然后在进入另一条路径

现在我们有了path，可以自己模拟一下怎么走的，但发现剪枝问题如何解决呢？？？

此时可以在设一个全局变量，也就是bool check[]，这里面存储每个元素是否已经被使用了

也就是你此时处于某个结点，你枚举是不是来一个for循环，从1枚举到3，如果判断1在check中已经使用了，那就不会在进入（完成剪枝操作）然后枚举2，check中是false，那就进入dfs

2.dfs函数：仅需关心每一个结点所做的事情

dfs：枚举数字

3.细节问题 

关心三点：1.回溯：干掉path最后一个元素，还要把check中对应位置改为true；

                  2.剪枝：通过check来完成剪枝

                  3.递归出口：遇到叶子结点，把path添加到ret即可 

代码编写： 

递归什么时候结束？？？

看第一个for循环

也就是你第一个位置填1，进去枚举所有以1开头的所有情况

下一次循环2，第一个位置填2，进去枚举所有以2开头的所有情况

下一次循环3，第一个位置填3，进行枚举所有以3开头的情况

第一个枚举完1/2/3后循环结束，dfs函数调用结束