本文目录
1 中文题目
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
示例：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
输入：nums = [0,1]
输出：[[0,1],[1,0]]
输入：nums = [1]
输出：[[1]]
提示：
- 1 ≤ n u m s . l e n g t h ≤ 6 1 \leq nums.length \leq 6 1≤nums.length≤6
- − 10 ≤ n u m s [ i ] ≤ 10 -10 \leq nums[i] \leq 10 −10≤nums[i]≤10
nums中的所有整数互不相同
2 求解方法：回溯法
2.1 方法思路
方法核心
使用回溯法并通过交换元素的方式实现全排列，对于每个位置，将其后面的每个数字（包括自己）都尝试放到当前位置，然后递归处理剩余位置，完成后再将元素换回原位，通过这种方式避免使用额外的标记数组和临时数组，达到空间复杂度的最优。
实现步骤
(1)初始化阶段：
- 创建结果列表用于存储所有排列
- 获取输入数组的长度
- 定义回溯函数，参数为当前待填充的位置
(2)回溯过程：
- 如果当前位置达到数组末尾，说明找到一个完整排列
- 将当前位置与其后的每个位置（包括自身）进行交换
- 递归处理下一个位置
- 处理完成后将元素换回原位，保持状态不变
(3)状态恢复：
- 每次递归返回前都要将交换的元素换回原位
- 确保不影响下一次交换的正确性
(4)结果收集：
- 当填充完所有位置时，将当前排列加入结果集
- 注意要创建当前数组的副本
方法示例
以输入 nums = [1,2,3] 为例：
初始状态：
nums = [1,2,3]
result = []
递归过程详解：
1. first = 0:
1.1 i = 0: 交换nums[0]和nums[0]：[1,2,3]
递归到first = 1
1.1.1 i = 1: 交换nums[1]和nums[1]：[1,2,3]
递归到first = 2
1.1.1.1 i = 2: 交换nums[2]和nums[2]：[1,2,3]
递归到first = 3，添加排列[1,2,3]
恢复：[1,2,3]
1.1.2 i = 2: 交换nums[1]和nums[2]：[1,3,2]
递归到first = 3，添加排列[1,3,2]
恢复：[1,2,3]
恢复：[1,2,3]
1.2 i = 1: 交换nums[0]和nums[1]：[2,1,3]
递归到first = 1
1.2.1 i = 1: 交换nums[1]和nums[1]：[2,1,3]
递归到first = 2
添加排列[2,1,3]
1.2.2 i = 2: 交换nums[1]和nums[2]：[2,3,1]
递归到first = 3，添加排列[2,3,1]
恢复：[2,1,3]
恢复：[1,2,3]
1.3 i = 2: 交换nums[0]和nums[2]：[3,2,1]
递归到first = 1
1.3.1 i = 1: 交换nums[1]和nums[1]：[3,2,1]
递归到first = 2，添加排列[3,2,1]
1.3.2 i = 2: 交换nums[1]和nums[2]：[3,1,2]
递归到first = 3，添加排列[3,1,2]
恢复：[3,2,1]
恢复：[1,2,3]
最终结果：
result = [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2]]
2.2 Python代码
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
# 结果列表
result = []
n = len(nums)
def backtrack(first = 0):
# 如果所有数都填完了，将当前排列添加到结果中
if first == n:
result.append(nums[:])
return
# 对当前位置之后的所有数字进行尝试
for i in range(first, n):
# 将当前数字交换到待填充的位置
nums[first], nums[i] = nums[i], nums[first]
# 递归填充下一个位置
backtrack(first + 1)
# 恢复现场，将数字换回原位
nums[first], nums[i] = nums[i], nums[first]
# 从第一个位置开始回溯
backtrack()
return result
2.3 复杂度分析
- 时间复杂度：O(n!)
- 回溯树的每个分支都代表一种可能的排列。树的总节点数量就是O(n!)
- 每个节点的操作（包括交换和可能的复制）都是O(1)级别的
- 空间复杂度：O(n)
- 递归调用栈的深度为O(n)
- 不需要额外的标记数组
3 题目总结
题目难度：中等
数据结构：数组
应用算法：回溯法