LeetCode 46. 全排列

yiluolion 2020-04-26 原文

46. 全排列

题目来源：https://leetcode-cn.com/problems/permutations/

题目

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

示例:

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

解题思路

思路：深度优化搜索

先看题目，以所给数组 [1, 2, 3] 的全排列为例：

以 1 开始，全排列有：[1,2,3], [1,3,2]；
以 2 开始，全排列有 [2,1,3], [2,3,1]；
以 3 开始，全排列有 [3,1,2], [3,2,1]。

从上面的情况，可以看出。枚举每个每一位可能出现的情况，已选择的数字在下面的选择则不能出现。按照这个做法，所有的情况将能够罗列出来。这里其实就是执行一次深度优先搜索，从根节点到叶子节点形成的路径就是一个全排列。

按照这种思路，沿用上面的例子，从空列表 [] 开始，以 1 开始为例。现在确定以 1 开始，则列表为 [1]，现在选择 [2] 和 [3] 之中的一个，先选 2，最后剩下的只有数字 3，所以形成全排列 [1, 2, 3]。

已知还有一种情况，也就是 [1, 3, 2]，那么如何实现从 [1, 2, 3] 到 [1, 3, 2] 的变化。深度优先搜索是如何实现的？其实是从 [1, 2, 3] 回到 [1, 2] 的情况，撤销数字 3，因为当前层只能选择 3，所以再撤销 2 的选择，这样后面的程序则能在选择 3 的时候后续也能选择 2。

代码实现

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        def _dfs(nums, depth, pmt, be_selected, length, ans):
            # 表示深度优化搜索的深度等于数组长度时，这个时候表示全排列已经生成
            # 也就是符合情况的选择已经选择完毕
            # 将这个全排列的情况添加到列表中
            # 这里需要注意，pmt 在参数传递是引用传递，拷贝一份添加到结果中
            if depth == length:
                ans.append(pmt[:])
                return

            # 开始遍历
            for i in range(length):
                # be_selected，表示原数组中的元素的状态，是否被选择，是为 True，否为 False
                if not be_selected[i]:
                    # 当元素被选择时，改变状态
                    be_selected[i] = True
                    # 将元素添加到 pmt 中，以构成后续
                    pmt.append(nums[i])
                    # 向下一层进行遍历
                    _dfs(nums, depth + 1, pmt, be_selected, length, ans)
                    # 遍历结束时，进行回溯，这个时候状态要进行重置
                    # 如上面说的 `[1, 2, 3]` 到 `[1, 3, 2]` 中变化，要撤销 3，再撤销 2，重新选择
                    # 状态改变
                    be_selected[i] = False
                    # 撤销
                    pmt.pop()

        length = len(nums)
        if length == 0:
            return []

        be_selected = [False] * length
        ans = []
        _dfs(nums, 0, [], be_selected, length, ans)
        return ans