LeetCode 46. 全排列
文章目录46. 全排列题目解题思路代码实现实现结果
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
实现结果
以上就是使用深度优化搜索的思想，解决《46. 全排列》的问题的主要内容，主要需要注意的是状态重置。
欢迎关注微信公众号《书所集录》
作者："大梦三千秋
