LC46　全排列¶

中等通过率 80.1%python3核心代码模式回溯样例通过牛客 AC数组回溯

一句话

每层决定排列的第几个位置放谁，used 标记哪些下标已被占用。

解题思路¶

这题考什么¶

回溯的标准骨架，关键在于排列与组合的枚举方式不同：组合题每层从 start 往后选，靠「不回头」保证同一批元素只出现一种顺序；排列题关心顺序，同一批元素的每种顺序都算一个解，所以每层都要从下标 0 扫到 n-1，靠 used 数组排除已经放进 path 的下标。

dfs():
    len(path) == n  ->  收下一份答案
    否则 for j in 0 .. n-1:
        used[j] 为真就跳过（这个下标已经在 path 里了）
        选：   path 追加 nums[j]，used[j] 置真
        递归： 去决定下一个位置
        撤销： path 弹出末位，used[j] 置假

「选择 -> 递归 -> 撤销」三步缺一不可。撤销时两处状态都要还原：只弹 path 不还原 used，那个下标就会被永久锁死，后续分支再也用不到它， n = 3 时答案会从 6 条塌成 1 条。深搜与回溯的通用写法见 DFS 深度优先搜索。

数据规模与复杂度¶

1 <= nums.length <= 6，元素互不相同，取值 -10 到 10。排列共 n 的阶乘条，n = 6 时是 720 条；每条要拷贝一份长度 6 的列表，时间 O(n 乘 n 的阶乘) 约 4300 次基本操作，指数级搜索在这个量级完全够用。递归深度只有 6，空间 O(n)：path 与 used 各一条，答案本身不计。

坑在哪¶

每层必须从下标 0 扫起，不能像组合题那样从 start 扫起。写成 start 的话产出的是子集而非排列，[1,2,3] 只会得到一条 [1,2,3]。
撤销要成对：path.pop() 与 used[j] = False 缺一不可。只恢复一处，后面的分支会读到脏状态——漏掉 used 还原是这题最常见的错法。
收答案时必须写 path[:] 做一份拷贝。path 是全程复用的同一个列表，直接追加它本身的话，res 里存的全是同一个对象的引用，回溯结束时 path 已被弹空，输出会变成一堆空列表。
used 标记的是下标不是数值。本题元素互不相同，两种写法碰巧等价；但一旦有重复元素（LC47 的形态），按数值标记会连同重复值的合法排列一起丢掉。按下标标记是通用写法，没有理由退化。
本题在 meta.json 的 judge 里配了 unordered：题面明写「可以按任意顺序返回答案」，解与解之间没有先后语义。但放宽仅限顶层—— 每个排列内部的元素顺序就是答案本身，[1,2,3] 与 [3,2,1] 是两个不同的解，绝不能一起放宽，否则这题就没有意义了。顺序放宽也不等于内容放宽：同一个排列吐两遍照样判错，本题的不重复由 used 保证（每个下标在一条路径上只出现一次）。
交换法（把 nums[j] 换到当前位置再递归）同样能枚举全排列，代码更短，但交换会打乱剩余元素的相对顺序，产出不成字典序；本题顶层顺序被放宽，两种写法都能过，选 used 版是因为它的不变量更直白。

样例复核¶

nums = [1,2,3]：第 0 位依次取 1、2、3，每种情况下第 1 位从剩下两个里取，第 2 位只剩一个，产出 [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]，共 3 的阶乘 = 6 条，与样例一致。

参考实现¶

solutions/leetcode/LC46/sol.py
from typing import List, Optional


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        # res 收答案，path 是当前正在拼的排列，used 记录哪些**下标**已被占用
        res = []
        path = []
        used = [False] * n

        def dfs() -> None:
            # 每个位置都填满就收一份；path[:] 是必需的拷贝，path 本身还要继续被改
            if len(path) == n:
                res.append(path[:])
                return
            # 每层都从下标 0 扫起（组合题才从 start 扫起），顺序不同的排列都要算
            for j in range(n):
                if used[j]:
                    continue        # 这个下标的元素已经在 path 里了，不能再放一次
                used[j] = True      # 选：占用下标 j
                path.append(nums[j])
                dfs()               # 递归：去决定下一个位置放谁
                # 撤销要成对：只还原一处，后面的分支就会读到脏状态
                path.pop()
                used[j] = False

        dfs()
        return res

LC46 全排列¶