全排列

更新: 7/4/2026 字数: 0 字时长: 0 分钟

题目描述

给定一个不含重复数字的整数数组 nums，返回其所有可能的全排列。排列之间顺序不限，但每个排列内部元素顺序不同即视为不同排列。

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

长度为的数组共有个全排列（样例中个）。

全排列的递归决策树：从空到六个叶子结果

思路拆解

暴力直觉：逐位枚举 + 事后判重

最朴素的想法是开层循环，第一位取谁、第二位取谁……全都枚举一遍，最后再筛掉“同一个数字用了两次”的非法组合。但循环层数取决于，无法写成通用代码，而且大量枚举出来的组合都要被丢弃，效率低下。

暴力解法的问题

写死层嵌套循环既不通用，又会产生大量非法组合再回头过滤。我们需要一种自动按层展开、且天然避免重复选取的框架——这就是回溯。

最优解法：回溯（选择 → 递归 → 撤销）

把构造排列看成一棵决策树：树根是空路径，第 1 层决定“第一个位置放哪个数”，第 2 层决定“第二个位置放哪个数”……走到第层（路径填满）就得到一个完整排列。回溯就是对这棵树做深度优先搜索。

核心思路

回溯的三步循环是：做选择（把一个未用过的数字加入路径、标记为已用）→ 递归（去决定下一个位置）→ 撤销选择（把它移出路径、恢复未用状态，好让同层尝试别的数字）。用一个 used[] 布尔数组标记哪些下标已在当前路径中，就能保证每个数字在一条路径里只出现一次。

回溯的“选择—探索—撤销”循环与 used 标记

为什么必须“撤销”？ 因为 path 和 used 在整棵递归树中是共享的同一份状态。当一条分支探索完返回时，如果不把刚才的选择撤销，这些残留状态会污染同层的下一个分支，导致排列出错。撤销让每次回到某个节点时，状态都恢复成“刚进入该节点”的样子。

下面的交互动画完整演示对 [1, 2, 3] 的回溯过程：绿色=本步选择、橙色=本步撤销、灰色=已用尽，右侧实时收集所有排列，可单步、自动播放与重置：

回溯 · 全排列演示

样例输入：[1, 2, 3]

候选数字（灰色 = 已用，绿色 = 本步选择，橙色 = 本步撤销）

当前路径 path（递归栈，深度 = 0）

（空）

已收集排列 0 / 6

尚未收集

回溯框架：path 是当前排列，used 标记哪些数字已用过。每层从所有未使用的数字里挑一个填入。

步骤 0 / 37

完整代码

/**
 * 全排列（回溯）
 * @param {number[]} nums 不含重复数字
 * @return {number[][]} 所有排列
 */
function permute(nums) {
  const res = []
  const path = []
  const used = new Array(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
}

点击展开：交换法（另一种 O(n!) 写法，原地生成）

// 通过交换 nums[start] 与后续每个元素来固定第 start 位
function permute(nums) {
  const res = []
  const dfs = (start) => {
    if (start === nums.length) {
      res.push([...nums])
      return
    }
    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]] // 选择
      dfs(start + 1)
      [nums[start], nums[i]] = [nums[i], nums[start]] // 撤销
    }
  }
  dfs(0)
  return res
}

复杂度分析

设为数组长度。

解法	时间复杂度	空间复杂度	说明
回溯（used 标记）			共个排列，每个拷贝耗；递归深度
交换法			原地交换省去 used，递归栈仍为

时间复杂度下界就是 ——因为输出规模本身就是个排列，无法更快。中的因子来自把每个长度为的排列拷贝进结果集。空间不计输出时为（递归栈 + path + used）。

边界与易错点

易错点

收集结果要拷贝：res.push([...path]) 必须深拷贝。若直接 res.push(path)，后续对 path 的增删会连带改掉已存进结果的引用，最终得到一堆空数组。
撤销必须与选择成对出现：path.push / used[i]=true 之后，递归返回时一定要 path.pop / used[i]=false，否则状态污染。
used[i] 判断别漏：忘记 if (used[i]) continue 会把已用数字再选一次，产生 [1,1,1] 这类非法排列。
含重复元素的变体：若 nums 含重复数字（全排列 II），需先排序，再加剪枝 if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) continue 去重；本题声明无重复，无需此步。
空数组：nums = [] 时应返回 [[]]（一个空排列），回溯框架天然满足——path.length === 0 === nums.length，直接收集空路径。
别用全局可变结构做返回值：确保 res 内每个排列相互独立。

一句话总结

把排列构造想成一棵决策树，回溯 = 选择 → 递归 → 撤销，配一个 used 标记避免重复选取，即可穷举全部个排列。

全排列 ​

题目描述 ​

思路拆解 ​

暴力直觉：逐位枚举 + 事后判重 ​

最优解法：回溯（选择 → 递归 → 撤销） ​

完整代码 ​

复杂度分析 ​

边界与易错点 ​

全排列