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]
]
分析
遇到全排列，所有可能等关键字，我们需要考虑DFS、回溯等解法。
这道题算是比较基础的题目，提供两种解法：
- python内置函数
- DFS 深度优先解题
解题1 内置函数：
from itertools import permutations
class Solution:
def permute(self, nums):
return list(permutations(nums))
解题2 DFS：
class Solution:
def permute(self, nums):
ret = []
path = []
def dfs(li):
if len(li) == len(path):
ret.append(path[:])
for i in li:
if i not in path:
path.append(i)
dfs(li)
path.pop()
dfs(nums)
return ret
47.全排列II
https://leetcode-cn.com/problems/permutations-ii/
难度：中等
题目：
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
提示：
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
示例：
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
分析
这道题是 46.全排列的进阶版本。
当然，我们可以通过稍微修改46题的临时存储格式，来暴力AC这道题，如解法一。
但解法一种只是进行了单纯的回溯，在剪枝方面做得很不好，多出了很多不必要的循环，导致执行时间较长。
那么，针对不重复的序列，我们应该如何操作呢？
我们只需要对数组进行排序后，多使用一个列表用于记录该数组的数字是否使用过即可。
解题1 暴力回溯：
class Solution:
def permuteUnique(self, nums):
ret = []
path = {}
def dfs(li):
if len(li) == len(path) and list(path.values()) not in ret:
ret.append(list(path.values()))
for i in range(len(li)):
if i not in path:
path[i] = li[i]
dfs(li)
path.pop(i)
dfs(nums)
return ret
解题2 合理剪枝：
class Solution:
def permuteUnique(self, nums):
ret = []
nums.sort()
stage = [0 for _ in nums]
path = []
def dfs(li):
if len(li) == len(path):
ret.append(path[:])
return
for i in range(len(li)):
if stage[i] == 1:
continue
if i > 0 and li[i] == li[i - 1] and stage[i - 1] == 0:
continue
path.append(li[i])
stage[i] = 1
dfs(li)
path.pop()
stage[i] = 0
dfs(nums)
return ret
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
