LeetCode 46. 全排列

约 5 分钟
文章信息 31 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 200-500 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 华为 微软 亚马逊 美团 拼多多 京东 小米 百度 小红书 快手 滴滴 携程 B站 虾皮 vivo 商汤 旷视 陌陌 猿辅导 图森
标签
数组 回溯

题目描述

✅ 46. 全排列

image-20260928183642202

题意分析

给定一个元素互不相同的数组，返回这些元素的所有排列。每个排列都必须恰好使用每个元素一次，元素的先后顺序不同就算不同结果，答案不要求按特定顺序返回。

可以把一个排列看成依次填满 n 个位置：第一个位置可以选任意元素，后面的每个位置只能选当前排列里还没用过的元素。题目没有重复值，因此不需要额外排序或去重，关键是枚举所有选择，并且不在同一条路径中重复使用元素。

解法：回溯 + used 标记

核心思路

[!blue]

用回溯逐个确定排列中的位置。path 保存已经填好的前缀，used[i] 表示 nums[i] 是否已经出现在这个前缀中。一次递归负责选择下一个位置的元素，递归深度就是已经选择的元素个数。

每层都从整个数组中枚举候选。若 used[i] 为真，说明这个元素已经用于当前位置之前，不能再选；否则将它加入 path 并标记为已使用，再递归填写后面的位置。这里不能像组合题一样只考虑更大的下标，因为排列需要允许后面的元素出现在前面的元素之前。

当 path 长度达到 n，所有元素都恰好使用了一次，这条路径就是一个完整答案。必须复制一份路径再存入结果，因为后续还会继续修改同一个 path；Java 创建新的列表，Go 创建新的底层数组，才能使已经保存的答案不受影响。

递归返回后，删除刚加入的末尾元素，并把对应的 used[i] 恢复为假，让状态回到选择之前。这样同一层的下一个候选会从相同前缀继续搜索，而不会继承上一条分支的选择。

每个合法排列的每一位都能在对应层被选到，因此不会遗漏；两个不同分支至少有一个位置选择不同的元素，而输入值互不相同，所以不会产生重复排列。

解题步骤

  1. 初始化空结果集、空路径 path 和全为假的 used 数组，开始回溯。
  2. 若路径长度等于数组长度，复制路径加入结果集，并结束当前层递归。
  3. 否则遍历所有下标，跳过 used[i] 为真的元素。
  4. 对可选元素设置 used[i] = true，追加到路径，递归填写下一个位置。
  5. 递归返回后删除路径末尾元素，并恢复 used[i] = false，继续尝试本层其他选择。

代码实现

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)$，用于路径、标记数组和递归栈；返回结果本身需要 $O(n \times n!)$ 空间。

关键点总结

[!green]

  • 每层都从全部元素中选择一个尚未使用的元素。
  • 保存答案时必须复制 path，避免后续回溯修改已收集的结果。
  • “选择、递归、撤销”必须成对出现。

易错点总结

[!yellow]

  • 直接把 path 放入结果集，导致所有结果引用同一个可变对象。
  • 回溯后忘记删除路径末尾元素或重置 used[i]。
  • 像组合题一样只向后枚举下标，会遗漏元素顺序不同的排列。

相似题目

题目 难度 关联与区别
47. 全排列 II 中等 同样逐位置选择未使用元素，原题允许重复值，需要额外限制同层等价选择。
31. 下一个排列 中等 本题一次枚举所有排列，原题只生成字典序紧邻的下一种排列。
补充题 206. 字典序全排列 中等 都通过回溯枚举排列并撤销选择；补充题先排序候选以直接按字典序输出。
60. 排列序列 困难 逐位选择未使用元素构造排列；本题输入互不相同可直接标记使用，该题用阶乘块大小直接定位第 k 个排列。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/83334596
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！