好的，我们这次来详细讲解 LeetCode 第 46 题「全排列」。

1. 题目描述

题目链接：https://leetcode.com/problems/permutations/

题目描述：
给定一个不含重复数字的数组 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 个元素，按照一定的顺序排列起来。排列数公式是 \(n!\)。

例如 [1,2,3] 的全排列是：

• 第一个位置可以是 1, 2, 3 中任意一个；
• 第二个位置从剩下的两个数中选一个；
• 第三个位置放最后一个数。

这样一共有 \(3 \times 2 \times 1 = 6\) 种排列。

题目要求我们生成所有可能的排列，而不是只计算排列的数量。

3. 思路分析

3.1 核心思想

我们可以把生成全排列的过程看作是一棵树的深度优先遍历（DFS）过程：

• 根节点：空列表 []，还没有选择任何数字。
• 第一层：分别选择 1, 2, 3 作为第一个数字。
• 第二层：从剩余数字中选一个作为第二个数字。
• 第三层：最后一个数字作为第三个数字。

到达叶子节点时，就得到了一个排列。

3.2 关键问题

在 DFS 过程中，我们需要知道：

1. 当前路径（已经选了哪些数字，顺序如何）
2. 剩余可选的数字（哪些数字还没被选）

4. 方法一：回溯法（使用 used 数组标记使用状态）

4.1 思路

• 用一个列表 path 记录当前已选的数字序列。
• 用一个布尔数组 used 记录每个数字是否已被使用。
• 递归函数 backtrack(path, used)：
  • 如果 path 长度等于 nums 长度，说明已经形成一个排列，加入结果列表。
  • 否则，遍历 nums 的每个索引 i：
    • 如果 nums[i] 还没被使用（used[i] == false）：
      • 标记 used[i] = true
      • 将 nums[i] 加入 path
      • 递归调用 backtrack
      • 回溯：从 path 中移除刚加入的数字，并标记 used[i] = false

4.2 代码实现（伪代码先理解）

def permute(nums):
    n = len(nums)
    res = []
    used = [False] * n
    
    def backtrack(path):
        if len(path) == n:
            res.append(path[:])  # 注意拷贝，因为 path 后面会变
            return
        for i in range(n):
            if not used[i]:
                used[i] = True
                path.append(nums[i])
                backtrack(path)
                path.pop()
                used[i] = False
                
    backtrack([])
    return res

4.3 执行过程示例（nums = [1,2,3]）

1. 初始：path = [], used = [False, False, False]
2. 第一层循环：
   • i=0: 选 1 → path=[1], used=[True,False,False]
     • 递归：剩余 [2,3] 可选
       • 选 2 → path=[1,2], 再选 3 → 得到 [1,2,3]
       • 选 3 → path=[1,3], 再选 2 → 得到 [1,3,2]
   • i=1: 选 2 → path=[2], 类似得到 [2,1,3], [2,3,1]
   • i=2: 选 3 → path=[3], 类似得到 [3,1,2], [3,2,1]

最终 res 收集到全部 6 个排列。

5. 方法二：回溯法（交换元素法）

5.1 思路

另一种思路是直接在原数组上通过交换来生成排列：

• 定义递归函数 backtrack(first)，其中 first 表示当前要填的位置索引。
• 对于 first 位置，依次将 first 和 first, first+1, ..., n-1 位置的元素交换。
• 交换后，nums[0..first] 是已确定的部分，nums[first+1..n-1] 是待选择的部分。
• 递归处理 backtrack(first + 1)。
• 递归返回后，再交换回来（回溯）。

5.2 代码实现

def permute(nums):
    res = []
    n = len(nums)
    
    def backtrack(first):
        if first == n:
            res.append(nums[:])  # 记录当前数组状态
            return
        for i in range(first, n):
            # 交换 nums[first] 和 nums[i]
            nums[first], nums[i] = nums[i], nums[first]
            backtrack(first + 1)
            # 回溯，交换回来
            nums[first], nums[i] = nums[i], nums[first]
            
    backtrack(0)
    return res

5.3 执行过程示例（nums = [1,2,3]）

• first=0:
  • i=0: 交换(0,0) → [1,2,3], 递归 first=1
    • first=1:
      • i=1: 交换(1,1) → [1,2,3], 递归 first=2 → 得到 [1,2,3]
      • i=2: 交换(1,2) → [1,3,2], 递归 first=2 → 得到 [1,3,2]
  • i=1: 交换(0,1) → [2,1,3], 递归 first=1 → 类似得到 [2,1,3], [2,3,1]
  • i=2: 交换(0,2) → [3,2,1], 递归 first=1 → 类似得到 [3,2,1], [3,1,2]

6. 复杂度分析

• 时间复杂度：O(n × n!)
  • 共有 n! 种排列。
  • 每种排列生成时需要 O(n) 时间（复制路径或执行操作）。
• 空间复杂度：O(n)
  • 递归栈深度为 n。
  • 用于 used 数组和 path 的空间为 O(n)。
  • 输出结果的空间是 O(n × n!)，但一般不计入空间复杂度（属于必要输出）。

7. 总结

• 全排列 是经典的回溯算法应用。
• 两种方法：
  1. used 数组法：直观易懂，适用于大多数排列、组合问题。
  2. 交换法：原地修改数组，节省了 used 数组空间，但改变了原数组（回溯会恢复）。
• 关键点：回溯时一定要恢复状态（pop 或交换回来），才能正确枚举所有情况。

这个题目是理解回溯算法的入门必做题目，希望这个一步步的讲解能帮助你彻底掌握！如果某个细节还不清楚，我可以进一步展开。