Frontend Interview

Appearance

46. 全排列 ​

题目链接：https://leetcode.cn/problems/permutations/

代码 ​

ts
function permute(nums: number[]): number[][] {
    const res = [];
    const len = nums.length;
    const path = new Array(len).fill(0);
    const onPath = new Array(len).fill(false);
    function dfs(i) {
        if (i === len) {
            res.push([...path]);
            return;
        }

        // 遍历所有数找到没用过的
        for (let j = 0; j < len; j++) {
            if (!onPath[j]) {
                path[i] = nums[j];
                onPath[j] = true;
                dfs(i + 1);
                onPath[j] = false;
            }
        }
    }
    dfs(0);
    return res;
};

思路 ​

使用回溯生成所有排列：

  1. 定义结果数组 res，用于保存所有合法排列
  2. 使用数组 path 记录当前已经选择的排列路径
  3. 使用布尔数组 onPath 标记哪些数字已经被使用过
  4. 递归函数 dfs(i) 表示当前要填排列中的第 i 个位置
  5. 每次枚举所有数字，挑选还没有使用过的数放到 path[i]
  6. 递归进入下一层后，再撤销当前选择，继续尝试其他分支

示例 ​

对于 nums = [1,2,3]：

  • 先选 1，继续递归构造后面的排列
  • 再选 2，接着选 3，得到 [1,2,3]
  • 回溯后改选 3，得到 [1,3,2]
  • 再回到更上一层，改为从 2 或 3 开头，继续同样过程

关键点 ​

  • path 用来保存当前递归路径上的排列结果

  • onPath[j] 用来避免同一个元素在同一条路径中被重复使用

  • 当 i === len 时，说明已经得到一个完整排列，可以加入结果集

  • 回溯的核心是“做选择、递归、撤销选择”

  • 时间复杂度 O(n×n!)，其中 n! 是排列总数，每个排列需要 O(n) 的拷贝成本

  • 空间复杂度 O(n)，主要是递归栈、path 和 onPath 的额外开销，不计结果数组