复盘 · LC 46 全排列

题目

题号：LeetCode 46
名称：全排列（Permutations）
难度：Medium
链接：leetcode.cn/problems/permutations
今日代码：46-全排列/index.js

题意

给定不含重复数字的数组 nums，返回所有可能的排列。顺序不同算不同结果，每个元素恰用一次。

示例：[1,2,3] → 6 种排列。
边界：n = 1 只返回 [nums]；n = 2 两种互换。

涉及算法

标签	一句话
回溯	做选择 → 递归 → 撤销；排列用 `used` 防重复选
DFS	决策树深度 = `n`，叶子即完整排列

教程对照：19 · 递归心智与回溯框架、20 · 回溯经典（全排列是 20 的精讲题）。

评价我的解法

你的思路：外层枚举第一个位置，内层 DFS 填后续位；isVisit 标记已用，visitNum === 0 时收叶子。能 AC，回溯的「选 / 探 / 撤」也做全了。

我的代码（摘自 46-全排列/index.js，不含本地测例）：

javascript

var permute = function (nums) {
  let len = nums.length;
  let isVisit = Array.from({ length: len }).fill(false);
  let tmpResArr = Array.from({ length: len }).fill(0);
  let resArr = [];
  function getNumPermute(index, depth) {
    isVisit[index] = true;
    tmpResArr[depth] = nums[index];
    let visitNum = 0;
    for (let i = 0; i < len; i++) {
      if (!isVisit[i]) {
        getNumPermute(i, depth + 1);
        visitNum++;
      }
    }
    if (visitNum === 0) {
      resArr.push([...tmpResArr]);
    }
    isVisit[index] = false;
  }
  for (let i = 0; i < len; i++) {
    getNumPermute(i, 0);
  }
  return resArr;
};

对在哪、糙在哪：

used + 撤销正确：每层 isVisit[index] = true/false 成对，不会漏撤。
叶子判定绕了一圈：用 visitNum === 0 等价于「没有未访问下标」，其实就是 depth + 1 === len。直接 if (depth + 1 === len) 或 path.length === n 更一眼看懂，面试口述也更顺。
外层 for + 内层全扫：等价于标准模板里 dfs 从 i = 0 起扫、used[i] 跳过——能过，但和教程 20 的「单入口 dfs() + for (i…)」比，多一层心智负担。
tmpResArr[depth] 代替 push/pop：功能等价，但 path.push / path.pop 是回溯默写模板，换题（子集、组合总和）时更好迁移。
复杂度：时间 O(n × n!)，空间 O(n) 递归栈 + 结果；与标准解一致。

小结：回溯核心会了，能过题；建议把写法收敛到教程 20 的 path + used + dfs() 单入口，叶子用 path.length === nums.length 收工。

最佳题解

标准回溯：单入口 DFS，used 防重选，路径满长即叶子：

javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const res = [];
  const path = [];
  const used = Array(nums.length).fill(false);

  const dfs = () => {
    if (path.length === nums.length) {
      res.push(path.slice());
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      dfs();
      path.pop();
      used[i] = false;
    }
  };

  dfs();
  return res;
};

时间 O(n × n!)，空间 O(n)（不含结果）。
为何更优：与 78/39/46 共用同一骨架；叶子条件、撤销、for 起点一眼可讲，换「排列 / 组合 / 子集」只改 used 与 start 规则。

关联题目

题	为何相关
47. 全排列 II	有重复元素；排序 + 同层去重
78. 子集	同一回溯框架，用 `start` 代替 `used`
39. 组合总和	可重复选；递归仍从 `i` 起
77. 组合	选够 `k` 个即停，练「与子集差一层」

一句话带走

全排列：used 标记 + path 满长收叶子 + 每层从 0 扫；口述时先讲决策树，再讲撤销。

复盘 · LC 46 全排列 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​