LeetCode刷题实战46：全排列-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 全排列，我们先来看题面：

https://leetcode-cn.com/problems/permutations/

Given a collection of distinct integers, return all possible permutations.

题意

给定一个没有重复数字的序列，返回其所有可能的全排列

样例

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解题

来源：

https://www.cnblogs.com/techflow/p/12636563.html

回溯法

我们在之前的文章当中分析过，全排列问题，可以看成是搜索问题，从而近似成八皇后问题。在八皇后问题当中，我们枚举的是棋盘的每一行当中的皇后放置的位置，而全排列其实也一样，我们要枚举每一个元素放置的位置。不过八皇后当中要求皇后除了不能同行同列之外还不能同对角线，而我们排列元素可以忽略这个要求。也就是说我们把每一行皇后放置的列号看成是每个元素摆放的位置，并且忽略同对角线的限制的话，那么八皇后问题和全排列问题就完全一样了。

如果还不理解，可以参考一下下图，我们给皇后编号，把皇后同样看成是序列当中的元素，那么八皇后的摆放位置刚好可以映射成一种排列。映射的方式非常简单，就是我们忽略行的信息，依次记录下皇后摆放的列号。

如果你能想通这两个看似完全不同的问题当中的相似之处，说明你对搜索问题的理解已经有些入门了。

思路清楚了，总之我们要枚举皇后摆放的状态。你可以按顺序遍历位置，然后枚举各个位置上放置的皇后，也可以顺序遍历皇后，枚举当前皇后可以放置的位置。两者是等价的，你可以根据自己的理解进行操作。

一般来说我喜欢遍历位置，枚举皇后。因为会引起冲突的是皇后，而不是位置。我们往往要判断皇后之间的关系以及皇后的状态，所以我们枚举皇后会比较贴合思路。

所以我们把之前八皇后的代码拿过来稍作修改即可，为了放置一个皇后重复放置在多个位置，我们需要存储皇后的状态，即有没有放置过。一般竞赛当中这种标记的变量称为flag，如果标记多个那就是flag数组。更多细节我们来看代码：

class Solution:
    def dfs(self, nums, n, i, cur, ret, flag):
        if i == n:
            ret.append(cur.copy())
            return
        for p in range(n):
            # 遍历所有元素
            # 如果p元素已经放置过了，跳过
            if flag[p]:
                continue
            # 当前位置放置p
            cur.append(nums[p])
            # flag[p]置为True
            flag[p] = True
            # 递归
            self.dfs(nums, n, i+1, cur, ret, flag)
            # 回溯
            cur.pop()
            flag[p] = False
        
    def permute(self, nums: List[int]) -> List[List[int]]:
        ret = []
        n = len(nums)
        # 记录元素i有没有放置过
        flag = [False for _ in range(n)]
        self.dfs(nums, n, 0, [], ret, flag)
        return ret

代码很短，细节也不多，只要理解了我们是按照顺序遍历位置，然后对于每一个位置遍历可以放置的元素，然后递归回溯即可。

其他方法

回溯法是这个问题的标准解法，那么这题还有没有其他方法呢？

其实是有的，也不难，在LeetCode31题的文章，也就是上面那个链接的文章当中我们解决了一个叫做下一个排列的问题。在这道题当中，我们给定一个序列，要求返回在它所有的全排列当中刚好字典序比它大1的排列，这个方法称为next_permutation。

如果还记得这道题的话就好办了，我们使用它很容易解出当前的问题。因为我们只需要获得给定序列的最小排列，然后不停地调用这个方法就好了，直到没有更大的序列退出即可。从最小的序列一直获取到最大的，当然就是全排列了。

在LeetCode31题当中，这是一个inplace的方法，没有返回值。并且当序列达到最大的时候，会自动再从最小的开始。我们需要稍稍修改一下，加上一个返回值，表示当前的序列是否是最大的。如果序列达到最大，说明我们可以不用继续往下寻找了，我们return一个True，表示可以退出了，否则我们return False，表示还有其他结果。

本质上我们是从最小的排列开始，不停地用一个叫做get_next的方法获取比当前序列大的下一个序列，当没有更大的序列的时候，说明我们已经获得了所有的排列，那么直接返回结果即可。如果忽略get_next当中的逻辑，这个代码其实只有几行：

其实这是一个取巧的办法，利用之前的思路我们完全不用思考，几乎可以无脑得到答案。但是从另外一个角度来说，这也是算法的魅力，毕竟通往终点的路往往不止一条。

最后我们来看下代码，如果你不懂怎么算next_permutation光看注释是很难看懂的，划到上面的链接看看吧。

class Solution:
    def get_next(self, nums: List[int]):
        """
        Do not return anything, modify nums in-place instead.
        """
        # 长度
        n = len(nums)
        # 记录图中i-1的位置
        pos = n - 1
        for i in range(n-1, 0, -1):
            # 如果降序破坏，说明找到了i
            if nums[i] > nums[i-1]:
                pos = i-1
                break
                
        for i in range(n-1, pos, -1):
            # 从最后开始找大于pos位置的
            if nums[i] > nums[pos]:
                # 先交换元素，在进行翻转
                nums[i], nums[pos] = nums[pos], nums[i]
                # 翻转[pos+1, n]区间
                nums[pos+1:] = nums[n:pos:-1]
                return False
        return True
        
        
    def permute(self, nums: List[int]) -> List[List[int]]:
        ret = []
        # 从小到大排序，获得最小排列
        nums = sorted(nums)
        ret.append(nums.copy())
        # 如果还有下一个排列则继续调用
        while not self.get_next(nums):
            # 要.copy()是因为Python中存储的引用，如果不加copy
            # 会导致当nums发生变化之后，ret中存储的数据也会变化
            ret.append(nums.copy())
        return ret