46. 全排列 (Medium)

专题归类： 08-回溯算法 LeetCode 链接： https://leetcode.cn/problems/permutations/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

给定一个不含重复数字的数组 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 中的所有整数互不相同

---

题目详细分析

数据范围含义：

• nums.length <= 6：规模很小，回溯的 O(n!) 复杂度完全可以接受。6! = 720，即便有常数开销也不会超时。
• 所有整数互不相同：不需要处理重复元素带来的去重问题，这是简化版本；若有重复则需要剪枝（参见 47-全排列 II）。

核心约束：

• 每个排列必须包含所有 n 个元素，且每个元素恰好出现一次。
• 顺序不同视为不同排列，这区别于组合问题。

边界条件：

• n = 1 时只有一种排列，选择列表只有一个。
• 空数组不会出现（长度至少为 1）。

---

小白版直白理解

就像你面前有 n 张写有不同数字的卡片，你要把它们排成一列。每次从没选过的卡片中抽一张放到队伍末尾，直到所有卡片都用完。你可以先把 1 放前面，然后 2、3；也可以先 2，再 1、3。把所有可能的排列方式都列出来，就是全排列。

这就好比你要把 3 个人排成一排拍照，所有可能的站位顺序就是全排列。

---

解题思路

思路一：回溯 + visited 数组（推荐）

核心思想： 标准的回溯算法，用 visited 数组标记已经选过的元素，每一层在”未使用”的元素中选择一个，递归到下一层。

决策树可视化（以 [1,2,3] 为例）：

                  []
         /        |        \
      [1]        [2]        [3]
     /   \      /   \      /   \
  [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
    |     |     |     |     |     |
 [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

每个叶子节点就是一个排列。

算法流程：

1. 初始化 res = [] 存放结果，visited = [False]*n 标记使用状态。
2. 定义回溯函数 backtrack(path)：
   • 如果 len(path) == n，找到一个排列，加入结果。
   • 遍历所有元素，跳过已使用的。
   • 标记当前元素已使用，将其加入路径。
   • 递归下一层。
   • 撤销选择：从路径中移除，取消标记。

def permute(nums):
    res = []
    n = len(nums)
    used = [False] * n
 
    def backtrack(path):
        # 终止条件：路径长度等于 nums 长度
        if len(path) == n:
            res.append(path[:])  # path[:] 创建副本，避免后续修改
            return
        # 遍历所有选择
        for i in range(n):
            if used[i]:
                continue  # 跳过已使用的元素
            # 做选择
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            # 撤销选择
            path.pop()
            used[i] = False
 
    backtrack([])
    return res

思路二：逐个插入法

核心思想： 从空排列开始，每次将一个新数字插入到已有排列的所有可能位置中。

以 [1,2,3] 为例：

初始: [[]]
插入 1: [[1]]
插入 2: [[2,1], [1,2]]
插入 3: [[3,2,1], [2,3,1], [2,1,3], [3,1,2], [1,3,2], [1,2,3]]

def permute(nums):
    res = [[]]  # 初始只有一个空排列
    for num in nums:
        new_res = []
        for perm in res:
            # 将 num 插入到 perm 的每个可能位置
            for i in range(len(perm) + 1):
                new_res.append(perm[:i] + [num] + perm[i:])
        res = new_res
    return res

时间复杂度： O(n x n!)，每次插入长度为 O(k)，总共有 n! 个排列。

---

易错点

1. 引用传递问题：res.append(path[:]) 而不是 res.append(path)。path 在回溯过程中会被修改，如果不创建副本，最终 res 中所有元素都会指向同一个空列表。
2. 忘记撤销选择：used[i] = False 和 path.pop() 必须成对出现。遗漏撤销会导致状态污染，使后续分支错误。
3. 数组越界：当 nums 只有一个元素时，常规逻辑仍然正确，但要确保不出现 nums[1] 的访问。
4. used 数组索引与 nums 索引的对应：used[i] 标记的是 nums[i] 是否被使用，而不是具体的数值。

---

框架提炼

回溯三要素模板：

def backtrack(路径, 选择列表):
    if 满足结束条件:
        结果集.append(路径[:])  # 注意副本
        return
 
    for 选择 in 选择列表:
        if 不合法(选择):
            continue  # 剪枝
        做选择(标记已用)
        backtrack(新路径, 新选择列表)
        撤销选择(清除标记)

排列问题的特点：

• 每层的选择列表 = 所有元素 - 已选的元素（由 visited 控制）。
• 终止条件 = 路径长度 == 总元素数（所有元素都选完）。
• 与组合/子集问题的区别：排列关心顺序，所以从全部元素中选；组合不关心顺序，所以用 start 控制只向后选。

---

关联题目

• 78-子集 — 同样是回溯，但子集不关心顺序，使用 start 参数而非 visited 数组，且每个节点都记录结果。
• 39-组合总和 — 可以重复选同一个元素，组合类回溯，用 start 控制方向。
• 51-N皇后 — 全排列的变体，每行选一个列位置，相当于对列索引做全排列，同时附加对角线约束。
• 47-全排列II — 包含重复数字的排列，需要在回溯中增加排序 + 重复剪枝。