LeetCode 补充题 206. 字典序全排列

2026-09-14 HGNULB 约 4 分钟

文章信息 2 个分类 2 个标签

分类

补充题中等

题目描述

:::fold-green 相关原题

LeetCode 原题： ✅ 46. 全排列

LeetCode 原题允许按任意顺序返回全排列；本文先排序数组副本，再按数值字典序输出，保留传入数组不变。

:::

给定互不相同的整数数组 nums，返回它的全部排列，整个结果按字典序递增。

示例 1：

输入： nums = [2,1]
输出： [[1,2],[2,1]]

提示：

1 <= nums.length <= 8
不修改传入的数组。

题意分析

本文要求按数值字典序排列整个结果，候选必须先按值排序。排列中的每个位置都可选任意未用元素，不能像子集搜索那样限制后续下标；用 used 记录当前排列已经使用的下标。

解法：排序 + 回溯

核心思路

[!blue]

先排序输入副本，使每一层能按从小到大的顺序选择候选。used[i] 表示下标 i 是否已在当前排列中，path 保存当前前缀。

为什么生成顺序就是字典序：两个排列第一次不同的位置决定大小；回溯会先完整输出较小候选对应的全部后缀，才进入较大候选分支，因此无需最后再排序结果。

每次选中后标记 used、追加 path，递归回来后撤销这两步。排列填满时保存路径副本，不能把继续变化的同一份路径直接交给所有结果。

解题步骤

复制并排序输入，准备 used 数组和空路径。

每层从小到大枚举所有未用元素，标记并加入路径后递归。

路径长度达到 n 时保存副本；递归返回后同时撤销路径末项和使用标记。

按搜索时的顺序返回结果，无需再次排序。

代码实现

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        nums = nums.clone();
        Arrays.sort(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;
        }
    }
}

import "sort"

func permute(nums []int) [][]int {
    nums = append([]int(nil), nums...)
    sort.Ints(nums)
    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\cdot n!)$。

空间复杂度：辅助空间 $O(n)$，输出空间 $O(n\cdot n!)$。

关键点总结

[!green]

先排序输入副本，再按下标从小到大选择尚未使用的元素；深度优先生成顺序即为字典序。

易错点总结

[!yellow]

排序副本以保护输入，同时保证本文的数值字典序；牛客对应版本采用输入位置优先级，顺序约定不同。

每层枚举全部未用下标，不能只选择上一次下标之后的元素。

返回后必须恢复 used 和 path，保存结果时复制路径。

相似题目

题目	难度	关联与区别
46. 全排列	中等	都通过回溯枚举互异元素的排列；该题不限制结果顺序，本题先排序副本、按升序选择候选，保证字典序输出。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/625632680192

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！