全排列 | 每日算法 · 变量语义法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给定一个不含重复数字的数组 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. 最直接：用 itertools.permutations 或三重循环硬枚举所有排列——思路对，但面试要写 DFS，且要理解为何能剪枝、如何回溯。

2. 重复在哪里？构造排列时，「已选前缀 + 剩余可选数字」这一状态会被反复访问；若允许同一数字选两次，会产生重复元素或非法排列。

3. 优化成回溯：用 path 记录当前前缀，用 used[i] 标记 nums[i] 是否已入选；每层从 0 到 n-1 扫描，跳过已用下标。

4. 终止条件：len(path) == n 时得到一个完整排列，将 path[:] 加入 ans；否则对每个未使用的 nums[i]：标记 → 追加 → 递归 → 撤销。

5. 题目保证元素互不相同，因此不需要「同层去重」；n ≤ 6，n! 最多 720，回溯完全可行。也可交换法原地生成，但 used 数组更直观。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`path`	list<int>	定义：当前正在构造的排列前缀（已选数字的有序序列）维护：每进入一层递归，从 `nums` 中选一个尚未使用的数追加到末尾更新：递归返回后 `pop` 撤销选择，保证兄弟分支从同一前缀出发
`used`	list<bool>	定义：长度 `n` 的标记数组，`used[i]` 表示 `nums[i]` 是否已在 `path` 中维护：选 `nums[i]` 前置 `used[i]=True`，回溯时恢复 `False` 更新：保证每个数字在全排列中恰好出现一次，避免重复选取
`ans`	list<list<int>>	定义：所有合法全排列的集合维护：当 `len(path) == n` 时，将 `path[:]` 的副本加入更新：每到达一棵 DFS 叶子追加一次；中途不收集半成品
`i`	int	定义：当前层尝试选取的 `nums` 下标维护：`for i in range(n)`，跳过 `used[i]` 为真的位置更新：同一层按固定顺序枚举候选，自然覆盖所有排列且不重复

⌨️ 落码步骤

1. 初始化 ans = []，used = [False] * n，空列表 path

2. 定义 DFS backtrack()：若 len(path) == n，将 path[:] 加入 ans 并返回

3. 遍历 i ∈ [0, n)：若 used[i] 为真则跳过

4. 选择 nums[i]：used[i]=True，path.append(nums[i])，递归 backtrack()，再 path.pop() 且 used[i]=False

5. 从 backtrack() 启动，返回 ans

💻 代码实现

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

        def backtrack() -> None:
            if len(path) == n:
                ans.append(path[:])
                return
            for i in range(n):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtrack()
                path.pop()
                used[i] = False

        backtrack()
        return ans

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;
        vector<bool> used(nums.size(), false);

        function<void()> dfs = [&]() {
            if (path.size() == nums.size()) {
                ans.push_back(path);
                return;
            }
            for (int i = 0; i < (int)nums.size(); i++) {
                if (used[i]) continue;
                used[i] = true;
                path.push_back(nums[i]);
                dfs();
                path.pop_back();
                used[i] = false;
            }
        };

        dfs();
        return ans;
    }
};
// 时间 O(n × n!)，空间 O(n)（递归栈 + used，不计输出）

📈 复杂度分析

时间复杂度 O(n × n!)

空间复杂度 O(n)（递归栈 + used，不计输出）

⚠️ 常见坑

❗ 收集答案时必须存 path[:]（或 C++ 里 push_back(path) 副本），不能直接 append(path)——否则 ans 里全是同一可变对象的引用。

❗ 回溯不撤销：递归返回后必须 pop 并恢复 used[i]，否则后续分支会带着脏状态，漏解或重复。

❗ 本题元素互不相同，同层不需要「跳过相同值」；若改成 permutations-ii（含重复数字），才要在同层对相同 nums[i] 去重。

🔍 必测边界 Case

Case 1：单元素

nums = [1] → [[1]]

Case 2：两个元素

nums = [0,1] → [[0,1],[1,0]]

Case 3：三个元素

nums = [1,2,3] → 6 种排列（3! = 6）

Case 4：含负数

nums = [-1,0,1] → 6 种排列（符号不影响回溯逻辑）

Case 5：最大规模

n = 6 → 720 种排列（仍在题目数据范围内）