LeetCode 46. 全排列

思路：深度优化搜索

先看题目，以所给数组 [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