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
