算法 - 全排列（Permutations）

Posted on

1. 题目

给定一个没有重复数字的数组 nums，返回其所有可能的全排列。可以按任意顺序返回答案。

示例:

1
2
输入: nums = [1,2,3]
输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

2. 解题思路

排列与组合/子集的最大区别：顺序有关，每层都要从头开始选。

2.1 回溯 + used 标记

  • 每一层递归都遍历整个数组，用 used[i] 记录 nums[i] 是否已在当前路径中。
  • 选中一个数就 path.push + used[i] = true，递归进入下一层；返回后撤销（pop + used[i] = false）。
  • 当 path.length === nums.length 时到达叶子节点，收集一个完整排列。

排列数 n!，故：

  • 时间复杂度：O(n·n!)，空间复杂度：O(n)。

2.2 交换法（原地生成，省空间）

在 index 位置，依次把后面的元素换到前面，递归处理 index+1。优点是不需要额外 used 数组，但顺序不保证字典序。

3. TypeScript 实现

3.1 回溯 + used

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function permute(nums: number[]): number[][] {
    const res: number[][] = [];
    const path: number[] = [];
    const used = new Array<boolean>(nums.length).fill(false);

    const backtrack = () => {
        if (path.length === nums.length) {
            res.push([...path]);   // 到达叶子才收集
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue; // 同一条路径不能重复用同一个元素
            used[i] = true;
            path.push(nums[i]);

            backtrack();

            path.pop();
            used[i] = false;       // 撤销选择
        }
    };

    backtrack();
    return res;
}

console.log(permute([1, 2, 3]));

3.2 交换法（原地）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function permuteSwap(nums: number[]): number[][] {
    const res: number[][] = [];

    const dfs = (first: number) => {
        if (first === nums.length) {
            res.push([...nums]);
            return;
        }
        for (let i = first; i < nums.length; i++) {
            [nums[first], nums[i]] = [nums[i], nums[first]];
            dfs(first + 1);
            [nums[first], nums[i]] = [nums[i], nums[first]]; // 回溯
        }
    };

    dfs(0);
    return res;
}

4. 面试延伸

  • 变体：Permutations II（含重复数字）：先排序，同层去重 if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) continue;——前一个相同值未被使用时跳过，保证相同元素只按固定相对顺序出现一次。
  • 子集 vs 组合 vs 排列 的递归起点：子集/组合用 start（不回头），排列每层从 0 开始（靠 used 去重）。这是最容易混的考点。
  • JS 中 path.push(...) 传引用会污染结果，务必 [...path] 或 path.slice() 拷贝。

难度：中等 | LeetCode 46 | 回溯法核心题