46. 全排列

题目链接（中等）

题目描述

给定一个不含重复数字的数组 nums，返回其 所有可能的全排列。你可以 按任意顺序 返回答案。

数据范围：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• 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]]

方法一：回溯 + 交换（原地修改）

思路及解法

把问题看作有 n 个排成一行的空格，从左往右依次填入 nums 中的数，每个数只能使用一次。用回溯法模拟这个过程。

核心技巧：把 nums 划分成左右两部分：

• 左边 [0, first-1]：已经填过的数；
• 右边 [first, n-1]：待填的数。

填第 first 个位置时，依次尝试用 [first, n-1] 里的数与 nums[first] 交换。交换后，[0, first] 就是已填部分，[first+1, n-1] 是待填部分。递归返回后，再交换回来，完成撤销。

递归终止条件：first == n，说明所有位置都填完了，把当前排列的副本加入答案。

举例：nums = [2,5,8,9,10]，已填到第 3 个位置，已填了 [8,9]，此时数组为 [8,9 | 2,5,10]。假设第 3 个位置要填 10，交换 2 和 10 后数组变为 [8,9,10 | 2,5]，继续保持“左边已填、右边待填”的状态。

这个方法生成的全排列不是按字典序的。如果题目要求字典序输出，请用标记数组法或字典序法。

代码

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        ans = []

        def backtrack(first: int = 0) -> None:
            # 所有位置都填完了
            if first == n:
                ans.append(nums[:])
                return

            for i in range(first, n):
                # 动态维护：把第 i 个数换到第 first 个位置
                nums[first], nums[i] = nums[i], nums[first]
                # 递归填下一个位置
                backtrack(first + 1)
                # 撤销操作
                nums[first], nums[i] = nums[i], nums[first]

        backtrack()
        return ans

复杂度分析

• 时间复杂度：$O(n \times n!)$。backtrack 的调用次数为 $O(n!)$，每次到达叶子节点（共 $n!$ 个）需要 $O(n)$ 时间复制当前排列到答案中。
• 空间复杂度：$O(n)$。除答案数组外，递归栈深度为 $n$。

方法二：回溯 + 标记数组

思路及解法

用一个布尔数组 used[i] 标记 nums[i] 是否已经被选入当前排列。每层从 0 开始遍历所有数，跳过已使用的，选择一个未使用的加入路径，标记后递归，递归返回后取消标记。

相比方法一，标记数组法思路更直观，也自然生成字典序的排列（因为每层都从小到大遍历）。

代码

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        ans = []
        cur = []
        used = [False] * n

        def dfs():
            if len(cur) == n:
                ans.append(cur[:])
                return
            for i in range(n):
                if not used[i]:
                    used[i] = True
                    cur.append(nums[i])
                    dfs()
                    cur.pop()
                    used[i] = False
        
        dfs()
        return ans

复杂度分析

• 时间复杂度：$O(n \times n!)$。共有 $n!$ 个排列，每个排列需要 $O(n)$ 时间复制到答案中。
• 空间复杂度：$O(n)$。used 数组和递归栈各占 $O(n)$。

方法三：字典序法（next_permutation）

思路及解法

如果要求按字典序输出，可以：

1. 先对 nums 排序，得到最小排列；
2. 不断调用「下一个排列」算法生成下一个排列，直到回到最小排列或生成 $n!$ 个排列。

或者直接用 Python 标准库 itertools.permutations：

from itertools import permutations

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        return [list(p) for p in permutations(nums)]

• 优点：代码极短，结果按字典序。
• 缺点：面试时如果要求手写回溯，用库函数可能不给分。

三种方法对比

方法	是否原地	结果顺序	是否需额外数组	特点
方法一：交换	是	非字典序	否	空间最省，需理解交换撤销
方法二：标记数组	否	字典序	是	思路最直观，推荐面试
方法三：字典序法 / itertools	否	字典序	视实现	代码最短，但不适合手写面试

总结

• 方法一（交换）：原地修改 nums，不需要额外数组，但生成顺序不是字典序，理解起来稍绕；
• 方法二（标记数组）：思路最直观，是回溯的标准模板，推荐面试时手写；
• 方法三（itertools）：代码最短，适合日常刷题，但不适合面试。

回溯通用模板：

def backtrack(路径, 选择列表):
    if 满足终止条件:
        记录答案（用副本）
        return
    for 选择 in 选择列表:
        做选择          # path.append(x) / used[i] = True
        backtrack(...)
        撤销选择        # path.pop() / used[i] = False

核心要点：

1. 记录答案时必须用副本：ans.append(path[:])，不能 ans.append(path)；
2. 递归返回后必须撤销选择，否则路径会残留上一层的内容；
3. 排列问题每层从 0 开始遍历，用 used 数组去重；组合问题用 start 参数控制起点。