LeetCode 46. 全排列（leetcode会员）

LeetCode 46. 全排列（leetcode会员）

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

实现结果

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。