难度: Medium
给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1] 输出：[[1]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums 中的所有整数 互不相同注意：本题与主站 46 题相同：https://leetcode-cn.com/problems/permutations/
运行时间: 18 ms
内存: 16.2 MB
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
# DFS
def dfs(res, cur):
if len(cur) == len(nums):
res.append(cur[:])
return res
for i in nums:
if i in cur:
continue
cur.append(i)
dfs(res, cur)
cur.pop()
return res
res, cur = [], []
return dfs(res, cur)
此题解采用了深度优先搜索（DFS）的方法来生成数组的所有可能全排列。递归函数 dfs 被用来尝试所有可能的元素组合。当递归的当前列表长度与输入数组长度相同时，说明形成了一个完整的排列，该排列被添加到结果列表中。在递归中，对输入数组中的每个元素进行遍历，如果元素已经存在于当前排列中，则跳过以避免重复使用；否则，将该元素添加到当前排列中，并继续递归。递归返回后，需要将最后添加的元素移除（回溯），以便尝试其他可能的元素添加。
时间复杂度: O(n * n!)
空间复杂度: O(n)
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
# 定义深度优先搜索的递归函数
def dfs(res, cur):
# 当当前列表长度等于nums长度时，说明形成了一个全排列
if len(cur) == len(nums):
res.append(cur[:])
return res
# 遍历nums中的每个元素
for i in nums:
# 如果元素已在当前列表中，则跳过以避免重复
if i in cur:
continue
# 否则添加该元素到当前列表cur
cur.append(i)
# 递归调用dfs
dfs(res, cur)
# 回溯，移除最后一个元素，尝试下一个可能的元素
cur.pop()
return res
# 初始化结果列表和当前排列列表
res, cur = [], []
# 开始递归
return dfs(res, cur)
在DFS递归函数中，通过检查当前元素是否已经存在于当前排列列表 `cur` 中来避免重复。在遍历输入数组 `nums` 的每个元素时，如果该元素已经在 `cur` 中，则跳过该元素的添加。这样确保了每个元素在每个全排列中只被使用一次。
在递归函数中使用 `cur.pop()` 进行回溯是为了在探索完一个元素的所有排列可能后，移除该元素，从而回退到之前的状态。这样可以在不影响之前状态的基础上，尝试其他兄弟元素的排列组合。通过这种方式，我们能够探索完所有可能的排列组合，实现全排列。
在DFS递归实现中，全排列的顺序由递归和元素添加的先后顺序决定。由于是深度优先搜索，递归将自然地探索每一种可能的排列，并按照探索到它们的顺序将它们添加到结果列表 `res` 中。这种方法不需要额外的操作来保证顺序，因为所有的排列都将在探索过程中自然生成，并按照生成的顺序返回，满足题目的要求。