全排列 图解题解

全排列这道题真正在问什么

给一个不含重复数字的数组 nums，返回它所有可能的排列，顺序不限。比如 [1, 2, 3] 有 6 种排法。这题要的不是「有几种」，而是把每种排列本身都列出来——答案规模就是 n! 个，绕不开逐一生成，真正的考点是：怎么生成得不重、不漏、代码还能对任意 n 通用。

为什么全排列要用回溯而不是嵌套循环

最直觉的想法是写循环：第一层挑第 1 个位置放谁，第二层挑第 2 个位置，一直嵌套下去。三个数写三层循环还行，可 n 是变量，循环层数没法在代码里写死——这条路在结构上就走不通。

关键观察是：生成一个排列，本质是逐位做决策。第 1 位可以放任何一个数，第 2 位可以放任何一个还没用过的数，以此类推。所有决策展开是一棵树，叶子就是完整排列。要把叶子一个不漏地收齐，自然的做法就是深度优先搜索这棵决策树；而「不定层数的嵌套循环」正好被递归取代——每递归一层等于多套一层循环。这种一边做选择、探完再撤销选择的 DFS，就是回溯算法。

path 和 used 数组各自维护什么不变量

path 存当前已经排好的前缀，used 数组标记每个数是否已被 path 占用。两者始终同步：任何时刻 used 里为真的数，恰好就是 path 里的那些数。有了这条不变量，每层的候选就很干净——把 nums 扫一遍，跳过 used 为真的，剩下的都能放进当前位。当 path 长度等于 nums 长度，说明每个数各就各位，收集一份进结果。

很多人会把组合题的「起点 start」套过来做去重，这在排列题里是错的：start 只允许往后选，可排列恰恰要求前面选过位置的数之后还能出现在别的位置上。排列的去重维度是「这个数用没用过」，所以必须用 used 标记，而不是限制下标范围。

为什么递归回来必须撤销选择

整棵决策树共用同一份 path 和 used，这是回溯省空间的精髓，也是它最容易错的地方。递归返回意味着「以刚才那个选择开头的分支已经探完」，此时必须把这个数从 path 弹出、used 复位，让本层状态恢复到做选择之前，才能公平地尝试下一个候选。不撤销的话，path 会越堆越长、used 永远占着，后面的分支全部建立在脏状态上。

还有一个隐蔽的坑：收集答案时要写 res.append(path[:])，存 path 的拷贝而不是 path 本身。因为 path 之后还会被反复修改，存引用会让结果里所有排列最终指向同一个被清空的列表。

复杂度怎么算，重复数字怎么办

时间 O(n·n!)：决策树有 n! 个叶子，每到一个叶子要把长度为 n 的 path 拷贝进结果，这一步就贡献了主要成本。空间 O(n)：递归深度、path、used 都只随 n 线性增长，结果本身不计。

本题保证数字互不相同；如果数组含重复数字（LeetCode 47 全排列 II），要先排序让相同的数相邻，再在每层循环里跳过「同层刚试过的相同值」，否则会生成重复排列。另一种省掉 used 的写法是交换法：把当前位与后面每个数交换后递归、再换回来，两种写法等价，used 法更直观。

Python

def permute(nums):
    res, path = [], []
    used = [False] * len(nums)
    def dfs():
        if len(path) == len(nums):
            res.append(path[:])      # 凑齐一个排列
            return
        for i in range(len(nums)):
            if used[i]: continue
            used[i] = True; path.append(nums[i])   # 选
            dfs()
            path.pop(); used[i] = False            # 撤销
    dfs()
    return res

Java

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    List<Integer> path = new ArrayList<>();
    dfs(nums, used, path, res);
    return res;
}
void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path)); return;   // 凑齐
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true; path.add(nums[i]);        // 选
        dfs(nums, used, path, res);
        path.remove(path.size() - 1); used[i] = false; // 撤销
    }
}

C++

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res; vector<int> path;
    vector<bool> used(nums.size(), false);
    function<void()> dfs = [&]() {
        if (path.size() == nums.size()) {
            res.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 res;
}