LeetCode46，实战递归回溯，生成全排列

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

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

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

回溯法

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

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

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

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

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

所以我们把之前八皇后的代码拿过来稍作修改即可，为了放置一个皇后重复放置在多个位置，我们需要存储皇后的状态，即有没有放置过。更多细节我们来看代码：

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的方法获取比当前序列大的下一个序列，当没有更大的序列的时候，说明我们已经获得了所有的排列，那么直接返回结果即可。

我们直接来看代码，从代码中获取更多细节：

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难度，并且题目的题意还是之前见过的，所以我想对你们来说也一定没有太大难度。