46. 全排列
一、算法逻辑（逐步通顺讲解每一步思路）
该算法使用了典型的 回溯（backtracking）+ 状态数组 思路，逐层递归生成排列。
题目目标：给定一个无重复整数数组 nums，返回其所有可能的全排列。
具体思路如下：
✅ 1️⃣ 初始化变量：
n = len(nums)：数组长度，表示排列长度；ans = []：最终结果列表，保存所有排列；path = [0] * n：当前正在构造的排列路径（长度固定为 n）；on_path = [False] * n：记录哪些下标的元素已经被使用，用来避免重复选择。
✅ 2️⃣ 定义递归函数 dfs(i)：表示当前正在构建第 i 位上的数字。
递归终止条件：当
i == n，说明整个排列已经构造完成，path中已有一个完整解；使用
path.copy()将当前路径添加到ans中（防止引用修改）。
✅ 3️⃣ 遍历所有可选数字：
遍历
nums中每个元素（通过索引j）；只有当
on_path[j] == False，才说明当前数字nums[j]还没被选过；将
nums[j]放入第i位的path[i]中，并标记为已使用；然后递归下一层
dfs(i+1)；回溯回来后，将
on_path[j]设为False，撤销选择，进入下一个分支。
✅ 4️⃣ 启动递归：
从 dfs(0) 开始，构造第 0 位，依次递归直到第 n-1 位，生成所有可能排列。
二、核心点总结
该算法的核心是：
使用回溯（DFS）方式按位构建排列，每一层递归尝试将所有未使用的数字填入当前位置，通过布尔数组标记状态，避免重复选择，实现全排列。
✅ 回溯模板典型写法（构造 + 撤销）；
✅ 使用显式路径数组 path[i] 来记录当前位置数字；
✅ 使用布尔标记数组 on_path 控制元素是否被使用；
✅ 整体结构是“选择—递归—撤销选择”的排列构造范式。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
path = [0] * n
on_path = [False] * n
def dfs(i:int) -> None:
if i == n:
ans.append(path.copy())
return
for j, on in enumerate(on_path):
if not on:
path[i] = nums[j]
on_path[j]=True
dfs(i+1)
on_path[j] = False
dfs(0)
return ans三、时间复杂度分析
一共有
n!个不同的排列；每个排列的构造过程为 O(n)，因为每一层选择都要扫描一遍
on_path。
所以总时间复杂度为：
O(n × n!)
四、空间复杂度分析
显式开销：
path数组：O(n)on_path数组：O(n)
隐式开销（递归栈）：
最多递归
n层（深度为 n）
所以总空间复杂度为：
O(n)（不包含输出）
如果包含所有输出结果，则为：
O(n × n!)（因为结果中包含 n! 个长度为 n 的排列）
✅ 总结一句话
该算法采用典型回溯框架，按位构造路径、记录状态、递归搜索，最终在 O(n × n!) 时间与 O(n) 空间下枚举出所有排列，是解决排列问题最通用、稳定的模板方案。