LeetCode46 回溯算法求全排列，这次是真全排列

今天是 LeetCode的26篇 文章，我们来实战一下全排列问题。

在之前的文章当中，我们讲过八皇后、回溯法，也提到了 全排列 ，但是毕竟没有真正写过。今天的LeetCode46题正是让我们生成给定元素的全排列。

题意很简单，只有一句话，给定一个没有重复元素的序列，让我们返回这个序列所有的全排列，并且我们不需要考虑这些排列的顺序。

回溯法

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

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

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

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

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

所以我们把之前八皇后的代码拿过来稍作修改即可，为了放置一个皇后重复放置在多个位置，我们需要存储皇后的状态，即有没有放置过。一般竞赛当中这种标记的变量称为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

代码很短，细节也不多，只要理解了我们是按照顺序遍历位置，然后对于每一个位置遍历可以放置的元素，然后递归回溯即可。基本上可以说是模板题，如果理解有难度的话，可以看一下之前详解八皇后问题的文章：

LeetCode 31：递归、回溯、八皇后、全排列一篇文章全讲清楚

其他方法

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

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

关于next_permutation的计算方法 也在链接里 ，如果有忘记的或者是最近关注的可以点下链接回顾一下，计算方法是完全一样的，我就不再重复了。

LeetCode 31：递归、回溯、八皇后、全排列一篇文章全讲清楚

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

在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

今天的问题并不难，只是 Medium难度 ，并且题目的题意还是之前见过的，主要是给大家加深一下回溯算法的映像用的，没什么太多的新内容。

文章的内容就是这些，如果觉得有所收获，请顺手点个 关注或者转发 吧，你们的举手之劳对我来说很重要。