好的，我们这次来详细学习 LeetCode 第 46 题：全排列（Permutations）。

1. 题目描述

题目：
给定一个不含重复数字的数组 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] <= 10
• nums 中的所有整数互不相同

2. 题意理解

“全排列”是指从 n 个不同元素中取出 n 个元素，按一定顺序排列，所有不同的排列情况。
例如 [1,2,3] 的全排列有 3! = 6 种。

关键点：

• 每个排列长度等于原数组长度。
• 每个元素在排列中必须出现且仅出现一次。
• 顺序不同视为不同排列。

3. 思路分析

3.1 直观想法

我们可以想象一个空列表，每次从剩下的数字中选一个放到当前位置，直到所有数字用完，就得到一个排列。
这个过程可以用回溯法（Backtracking）实现。

3.2 回溯法框架

回溯法基本结构：

1. 路径（path）：记录当前已选择的数字序列。
2. 选择列表（剩余可用的数字）。
3. 结束条件：当路径长度等于 nums 长度时，将路径加入结果列表。
4. 遍历选择：从剩余数字中依次选择一个加入路径，然后递归进入下一层，之后撤销选择（回溯）。

3.3 如何记录“已使用”的数字？

因为数字不重复，我们可以用一个 used 布尔数组来标记某个下标的数字是否已在当前路径中使用过。

4. 详细步骤推导（以 nums = [1,2,3] 为例）

初始：
path = []，used = [false, false, false]，result = []

第一层递归：

• 可选的数字索引有 0, 1, 2（对应数字 1, 2, 3）
• 先选索引 0（数字 1）：
  • path = [1]，used = [true, false, false]
  • 进入递归第二层

第二层（path=[1]）：

• 可选的索引是 1, 2（数字 2, 3）
• 先选索引 1（数字 2）：
  • path = [1, 2]，used = [true, true, false]
  • 进入递归第三层

第三层（path=[1,2]）：

• 只剩索引 2（数字 3）可选
  • path = [1, 2, 3]，长度达到 3 → 加入结果：[[1,2,3]]
  • 回溯：撤销选择 3（path 去掉 3，used[2]=false）

回到第二层（path=[1,2]），撤销选择 2（used[1]=false），然后选索引 2（数字 3）：

• path = [1, 3]，used = [true, false, true]
• 进入第三层：只剩数字 2 可选
• path = [1, 3, 2] → 加入结果：[[1,2,3], [1,3,2]]
• 回溯……

如此继续，直到第一层选过数字 1、数字 2、数字 3 的所有情况。

5. 代码实现（Python）

def permute(nums):
    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])  # 复制当前路径
            return
        for i in range(len(nums)):
            if not used[i]:
                # 做选择
                used[i] = True
                path.append(nums[i])
                # 进入下一层决策树
                backtrack(path, used)
                # 撤销选择
                path.pop()
                used[i] = False

    result = []
    backtrack([], [False] * len(nums))
    return result

6. 复杂度分析

• 时间复杂度：O(n × n!)
  全排列共有 n! 种，每种排列生成时需要 O(n) 时间复制到结果列表。
• 空间复杂度：O(n)
  递归栈深度为 n，used 数组和 path 数组均为 O(n) 空间（不算输出结果存储）。

7. 关键点总结

• 回溯法的核心是 选择 → 递归 → 撤销。
• 用 used 数组避免重复选择同一元素。
• 结束条件是路径长度等于原数组长度。
• 由于数字不重复，不需要去重处理（对比 LeetCode 第 47 题“全排列 II”就有重复数字，需要去重）。

这样一步步推导，你应该能清晰地理解全排列问题的回溯解法了。需要我进一步解释回溯过程中某一步的具体状态变化吗？