46. 全排列

题目描述

给定一个不含重复数字的数组 nums，返回其所有可能的全排列。

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

题型判断

每个位置都要从“尚未使用的数字”中选择一个，选择后继续处理下一个位置；走到底后撤销选择并尝试其他分支。这是典型回溯。

全排列与组合、子集问题的一个重要区别是：每一层都可以从整个数组中选择元素，只要该元素没有出现在当前路径中。因此循环每次都从索引 0 开始，不能使用 startIndex 限制选择范围。

例如生成 [2,1,3] 时，选择 2 之后，下一层仍然需要回头选择索引更小的 1。如果只允许向后选择，就会漏掉这个排列。

核心思路

递归过程中维护：

path：当前已经选择的排列前缀。
used[i]：nums[i] 是否已经出现在当前路径中。
当 path.length === nums.length 时，保存路径副本。

在每次进入递归时，都应满足以下状态关系：

used[i] 为 true ⇔ nums[i] 已经存在于当前 path 中

所以一次完整选择必须包含“做选择、继续递归、撤销选择”三个步骤：

used[i] = true;
path.push(nums[i]);

backtrack();

path.pop();
used[i] = false;

以 nums = [1,2,3] 为例，递归树如下：

[]
├─ [1]
│  ├─ [1,2]
│  │  └─ [1,2,3]
│  └─ [1,3]
│     └─ [1,3,2]
├─ [2]
│  ├─ [2,1]
│  │  └─ [2,1,3]
│  └─ [2,3]
│     └─ [2,3,1]
└─ [3]
   ├─ [3,1]
   │  └─ [3,1,2]
   └─ [3,2]
      └─ [3,2,1]

每深入一层，就确定排列中的一个位置；当路径长度等于 nums.length 时，得到一个完整排列。

代码实现

var permute = function (nums) {
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);

  const backtrack = () => {
    if (path.length === nums.length) {
      result.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 result;
};

复杂度与易错点

时间复杂度：O(n × n!)，共有 n! 个排列，复制每个排列需要 O(n)。
辅助空间复杂度：O(n)，路径、标记数组和递归深度均为线性。
返回结果占用 O(n × n!) 空间，共有 n! 个长度为 n 的排列。
保存结果时必须复制 path，否则所有结果会引用同一个数组。
回溯返回后必须同时撤销 path 和 used 状态。
每层循环必须从 0 开始；startIndex 适用于组合、子集等只向后选择的问题，不适用于全排列。

如果数组包含重复元素

本题保证数组元素互不相同，所以只需要通过 used[i] 防止同一个元素在一条路径中被重复选择。

如果数组允许包含重复元素，仅使用 used 仍然会生成重复排列。此时需要先排序，再增加同层去重：

nums.sort((a, b) => a - b);

for (let i = 0; i < nums.length; i++) {
  if (used[i]) continue;

  if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
    continue;
  }

  // 做选择、递归、撤销选择
}

两个判断的职责不同：

used[i]：防止同一个下标的元素在当前路径中被重复选择。
nums[i] === nums[i - 1] && !used[i - 1]：跳过同一层中值相同的重复选择，避免生成重复排列。

ON THIS PAGE

#46. 全排列

#题目描述

#题型判断

#核心思路

#代码实现

#复杂度与易错点