LeetCode 46. 全排列

2026-09-01 HGNULB 约 6 分钟

文章信息 29 个分类 4 个标签

分类

LeetCode CodeTop 中等已解决需复习 200-500 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度滴滴京东华为拼多多小米商汤旷视亚马逊虾皮图森携程哔哩哔哩小红书 LeetCode 热题 100 面试经典 150 题

题目描述

✅ 46. 全排列

题意分析

输入是一个数组 nums，要求返回它的全部排列。所谓排列，就是把 nums 里的每个元素恰好用一次重新排成一行，只有顺序不同；答案里各条排列之间的先后次序不限，怎么排都算对。

题面明确给了「元素互不相同」这个前提，它带来的第一个结论是：本题不需要任何去重逻辑。只要每次都从「还没用过的元素」里挑，两条排列一旦在某个位置选的元素不同，它们整条就不同；元素各不相同，也就不会出现两次挑到「值一样但算作两个」的情况。这正是本题与 47 全排列 II 的分界线——一旦允许重复元素，同一层里挑到两个相等的值会产出一模一样的排列，那时才必须补上判重手段。做本题时若下意识加上去重，属于无效代码；做 47 时若沿用本题写法，则一定会输出重复答案。

第二个结论关于答案规模：长度为 $n$ 的互不相同数组恰好有 $n!$ 条排列——第 1 个位置有 $n$ 种取法，第 2 个位置剩 $n-1$ 种，依次相乘即 $n \times (n-1) \times \cdots \times 1$。注意这是题目输出本身的体量，与用什么方法无关。既然光是把答案写出来就要写 $n!$ 条、每条 $n$ 个数，任何正确解法的运行时间都不可能低于 $\Omega(n \times n!)$，因此不存在多项式时间的做法，只能把所有可能的顺序逐一构造出来。这一点决定了本题的优化空间只在常数因子和额外空间上，不在数量级上——看到「输出规模即为下界」的题目，就不必再花时间去找什么巧妙公式了。

边界情况有两个值得先想清楚。n = 1 时唯一的排列是数组自身，答案形如 [[7]]，是一个含单条排列的列表，而不是空列表。n = 0 时按 $0! = 1$ 的约定应当返回一条空排列 [[]]，即答案里有一条什么都不含的排列；下文两份代码在这种输入下天然就是这个行为，无需特判。

解法：回溯 + used 标记

核心思路

用 path 记录当前排列，用 used[i] 标记 nums[i] 是否已选。每层枚举一个未使用元素加入路径；路径长度等于 n 时，保存一份快照。递归返回后撤销选择，继续尝试其他元素。

题目保证元素互不相同，因此不需要排序或去重。

解题步骤

初始化结果集、路径和 used 数组。

枚举所有未使用元素，标记后加入路径。

递归构造下一个位置，再撤销本次选择。

路径长度达到 n 时，复制路径并加入结果集。

代码实现

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(nums, new boolean[nums.length], new ArrayList<>(), ans);
        return ans;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> path,
                           List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, ans);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

func permute(nums []int) [][]int {
    ans := make([][]int, 0)
    used := make([]bool, len(nums))
    path := make([]int, 0, len(nums))

    var backtrack func()
    backtrack = func() {
        if len(path) == len(nums) {
            ans = append(ans, append([]int(nil), path...))
            return
        }

        for i, num := range nums {
            if used[i] {
                continue
            }
            used[i] = true
            path = append(path, num)
            backtrack()
            path = path[:len(path)-1]
            used[i] = false
        }
    }

    backtrack()
    return ans
}

复杂度分析

时间复杂度：$O(n \times n!)$，共有 $n!$ 个排列，每个排列需要复制 $n$ 个元素。

空间复杂度：$O(n)$，不计返回结果；路径、标记数组和递归栈最多占用线性空间。

关键点总结

每层都从全部元素中选择一个尚未使用的元素。

保存答案时必须复制 path，避免后续回溯修改已收集的结果。

“选择、递归、撤销”必须成对出现。

易错点总结

直接把 path 放入结果集，导致所有结果引用同一个可变对象。

回溯后忘记删除路径末尾元素或重置 used[i]。

像组合题一样只向后枚举下标，会遗漏元素顺序不同的排列。

相似题目

题目	难度	考察点
22. 括号生成	中等	候选只有两种字符，靠左右括号计数剪枝而非标记数组
31. 下一个排列	中等	只求字典序的下一条排列，$O(n)$ 原地扫描即可，无需搜索
39. 组合总和	中等	同一元素可无限次重复选取，递归时起点不前进
40. 组合总和 II	中等	元素可重复出现但每个只能用一次，需排序后同层跳过相等值
47. 全排列 II	中等	输入允许重复元素，必须补上同层去重才不会输出相同排列
51. N 皇后	困难	本质是求满足对角线约束的排列，需在选择时额外做冲突剪枝
60. 排列序列	困难	只要第 `k` 条排列，用阶乘直接定位每一位，不能枚举全部
77. 组合	中等	结果不计顺序且长度固定为 `k`，枚举起点递增而非从头开始
78. 子集	中等	每个节点都要收集答案，路径长度不必等于 `n`
90. 子集 II	中等	子集版本的重复元素处理，在 78 的基础上加同层去重
216. 组合总和 III	中等	候选固定为 1 到 9，同时受个数与和两个条件约束
784. 字母大小写全排列	中等	位置顺序不变，每个字母位上二选一（大写或小写），本质是子集型枚举
LCR 083. 全排列	中等	与本题完全同题，仅题号与题面表述不同
LCR 084. 全排列 II	中等	47 的同题版本，用于对照本题的去重差异
剑指 Offer 38. 字符串的排列	中等	对象是字符串且字符可能重复，需要去重并按字符串形式返回
面试题 08.07. 无重复字符串的排列组合	中等	字符互不相同，可直接照搬本题写法，只是把数组换成字符数组
面试题 08.08. 有重复字符串的排列组合	中等	字符可重复，是本题去重版在字符串上的对应题