全排列 

（递归树图之后会更新，两星期之内）

今天花时间来熟悉的是全排列，据网上资料透露常考，比较经典，同时能考察考生的递归的功底，进一步也能考察考生非递归的实现，所以很能考察考生的基本功。我一开始理解程序也有点困难所以画了个栈图，希望大家也都能搞明白，如果理解了给我点个赞吧，蟹蟹大家！

全排列是什么？

举个栗子：

将整型数组[1,2,3] 进行全排列，你将会得到[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]，总共是六个结果，根据给的整型数组的值，进行不同位置的排序，得到原数组中所有元素不同排列的结果。

为什么是六个结果？

根据全排列的计算公式：f(n)=n!(定义0!=1)

n代表我们的数组长度，我们的数组长度是3，所以将3带进去，我们能得到3 * 2 * 1 = 6

题目输入：

整数类型的array，array中的每个元素都是唯一的

解题思路：

例如我们有一个数组 [ 1, 2, 3 ] 我们需要对他们进行全排列，

我们选 1 作为第一个数字，然后我们需要对其他数字进行全排列，第二个数字可以是2 也可以是 3，所以我们获得了 [ 1, 2 ] 和 [ 1, 3 ]。然后我们再对接下来的数字进行全排列，我们就会得到结果 [ 1, 2, 3 ] 和 [ 1, 3, 2 ]。

如果我们 我们选择 2 作为第一个数字，我们将它从原来的数组中移除，那原数组就只剩下[ 1, 3 ]，接下来我们继续进行全排列，我们就获得了 [ 2, 1]，因为我们第二个数字选择了 1 所以我们需要在原数组中移除1，因此原数组只剩下 [3]，我们再对第三个数全排列选择，因此我们得到了[ 2, 1, 3 ]。第二次我们继续重复刚刚操作，我们就能得到 [ 2, 3, 1 ]这个数组。

全排列第二个数字

简单的总结一下上面的例子，

我们需要选择第一个数字，然后将它从原数组中移除，然后开始全排列第二个数字，然后再将它移除，再全排列第三个数字，直到原数组中的数字都被遍历完了，我们就得到全排列的答案。

中场回顾：

我们知道如何去选取第一个数字，第二个数字 ... 直到第n个数字，我们还介绍了总共有多少种可能性，因此我们在选择第一个数字的时候，我们有n种可能性，第二个数字的时候我们有n - 1种可能性，第三个数字我们有n - 2种可行性 ... 直到最后一个数字。

接下来是代码讲解，

这是代码的伪代码，我们会先写一个helper方法帮我们实现之前的所说的事情。

1. 在这个helper方法里面有三个参数 ———  arr, perm, perms 

    arr参数代表 array 意思是我们需要传入的原来的数组，如果我们要求[ 1，2，3 ]的全排列我们就输入[ 1，2，3 ]

    perm的意思是permutation，存储的是当前正在全排列的数组，比如我们一开始选择了 1 作为第一个数就传入 [ 1 ]

    perms的意思是permutations，存储的是全排列完成了的数组，例如我们得到了全排列的数组 [ 1，3，2 ]我们就能添加到perms里面

2. 如果arr是空的，就说明我们完成了一个全排列，因为我们每加入一个数到perm中我们就需要在原来的数组中移除相同的数字

3. 如果arr不是空的说明我们前排列哈没有完成，我们选择全排列中的第一个数字，然后将它从原数组中移除，然后将存储当前正在全排列的变量perm中。原数组[ 1, 2, 3 ]我们选择了 1 然后加入到perm中， perm就是 [ 1 ]，然后移除之后原数组就是[ 2, 3 ]。

4. 我们已经选择了第一个数，所以我们要对后面的数字进行全排列了，所以我们传入新的原数组，新的perm，和permutations（存储全排列好的对象的数组）到helper方法里面。

小总结一下：判断排列好没有，没有排列好就继续选择原数组中的元素，选择一个之后从原数组中移除，添加到正在全排列的变量 perm中，然后除了被选择得数字后面的数字也要进行全排列，所以再次调用helper方法！

空间复杂度讲解：

空间复杂度是O(n * n!)，我们创建了一个存储数组，存储全排列的结果，结果总共是N! 种，同时每个可能性长度是N，所以时间复杂度是O(n * n!)

时间复杂度讲解，

图1第一个判断列表是否为空我们需要执行 n！次，因为我们总共有n！种可能，当所有的原列表种的元素移除完了，才能证明我们的全排列做好了所以这里的时间复杂度是O(n！)。

我们每次想获得一种全排列的答案我们都需要遍历一整个列表所以这里的时间复杂度是O(n)。

我们每次还需要移除n个元素，因为移除完了所有的原列表中的元素，才能说明我们全排列完成了，这个时间复杂度是O(n)。

因此最终的时间复杂度是O(n! * n * n) 也就是O(n! * n^2)

图1

这个是对图1进行补充说明，最下面的叶子节点代表最终的全排列的结果，总共有n!个，我们需要通过n次的遍历才能拿到一个结果。我们同时也要移除n个元素。所以最终的时间是O(n! * n^2)

图2 图1的补充说明

代码

如果看不懂的可以拉下去看程序运行的栈图！！！！

需要没有注释的可以拉到最下面，

程序运行的栈图（可能用树状图会更好理解，稍后会更新树状图）

三个list对应着helper方法的三个参数  arr  perm perms   （arr 的意思是array， perm的意思是permutation， perms的意思是permutations

程序栈图

没有注释的版本

未优化版本

如果你成功看到这里，让我们来讲讲如何优化这个代码！

如何让我们的时间复杂度降低一个n

我们可以不需要移除list中的元素，取而代之的是我们使用指针，说明如图

小总结一下，我们想要做的事情是！选择一个数字，然后全排列它后面的数字和，选择了1 全排列 2 3 选择了 1 2 全排列后面的 3，再实际中我们的传的可能不是一个长度为3的数组，所以我们要一直全排列下去，直到整个数组全排列完成。然后我们 undo 也就是取消之前的操作，让他回到上一层。

伪代码

伪代码

伪代码的解释说明

时间复杂度和空间复杂度：

先说空间复杂度和上面是一样的也是O(n! * n)，因为有n！个结果，每个结果的长度是n

时间复杂度是 O(n! * n)，比较占用操作数的就是 if 判断下的数组添加操作，我们需要添加 n长度的答案，然后我们总共有n！个结果，else条件下面的 交换操作都是常数时间复杂度，也就是O(1)，所以我们总共是O(n! * n + 3)两个交换操作和一个方法调用操作，所以时间复杂度更接近O(n! * n)。

代码：

优化后的有注释的代码

栈图

代码栈图

优化过的版本

Reference：代码来自Algoexpert，以学习作为主要目的来分享的。

如果大家喜欢我的分享可以点一下喜欢谢谢！