跳到主要内容

全排列

问题​

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

示例：

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

来源：LeetCode 46. 全排列

答案​

方法一：回溯（推荐）​

核心思路：在每个位置做选择 → 递归到下一层 → 撤销选择（回溯）。

permute.ts
function permute(nums: number[]): number[][] {
  const result: number[][] = [];

  function backtrack(path: number[], used: boolean[]): void {
    // 终止条件：排列长度等于数组长度
    if (path.length === nums.length) {
      result.push([...path]); // 注意要拷贝！
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue; // 跳过已使用的元素

      // 做选择
      path.push(nums[i]);
      used[i] = true;

      // 递归
      backtrack(path, used);

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

  backtrack([], new Array(nums.length).fill(false));
  return result;
}

决策树：

                   []
         /         |         \
       [1]        [2]        [3]
      /   \      /   \      /   \
   [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
    |      |     |      |     |      |
 [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
复杂度分析
  • 时间复杂度：O(n×n!)O(n \times n!) — n! 个排列，每个需要 O(n)O(n) 复制
  • 空间复杂度：O(n)O(n) — 递归栈 + path + used
回溯模板
function backtrack(路径, 选择列表):
  if 满足终止条件:
    收集结果
    return

  for 选择 in 选择列表:
    做选择
    backtrack(路径, 选择列表)
    撤销选择

方法二：交换法（原地，无需 used 数组）​

通过交换元素来生成排列，不需要额外的 used 数组：

permuteSwap.ts
function permute(nums: number[]): number[][] {
  const result: number[][] = [];

  function backtrack(start: number): void {
    if (start === nums.length) {
      result.push([...nums]);
      return;
    }

    for (let i = start; i < nums.length; i++) {
      // 将 nums[i] 放到 start 位置
      [nums[start], nums[i]] = [nums[i], nums[start]];
      backtrack(start + 1);
      // 回溯：换回来
      [nums[start], nums[i]] = [nums[i], nums[start]];
    }
  }

  backtrack(0);
  return result;
}

图解：

nums = [1, 2, 3]

start=0:
  swap(0,0): [1,2,3] → start=1
    swap(1,1): [1,2,3] → start=2 → 收集 [1,2,3]
    swap(1,2): [1,3,2] → start=2 → 收集 [1,3,2]
  swap(0,1): [2,1,3] → start=1
    swap(1,1): [2,1,3] → 收集 [2,1,3]
    swap(1,2): [2,3,1] → 收集 [2,3,1]
  swap(0,2): [3,2,1] → start=1
    swap(1,1): [3,2,1] → 收集 [3,2,1]
    swap(1,2): [3,1,2] → 收集 [3,1,2]

方法三：插入法​

从一个元素开始，逐步在所有可能的位置插入新元素：

permuteInsert.ts
function permute(nums: number[]): number[][] {
  let result: number[][] = [[]];

  for (const num of nums) {
    const newResult: number[][] = [];

    for (const perm of result) {
      // 在 perm 的每个位置插入 num
      for (let i = 0; i <= perm.length; i++) {
        const copy = [...perm];
        copy.splice(i, 0, num);
        newResult.push(copy);
      }
    }

    result = newResult;
  }

  return result;
}

常见面试追问​

Q1: 如果数组有重复元素呢？(LeetCode 47)​

答案：排序后在同层跳过相同元素：

function permuteUnique(nums: number[]): number[][] {
  const result: number[][] = [];
  nums.sort((a, b) => a - b);

  function backtrack(path: number[], used: boolean[]): void {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      // 同层去重：如果前一个相同元素没有被使用，跳过
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;

      path.push(nums[i]);
      used[i] = true;
      backtrack(path, used);
      path.pop();
      used[i] = false;
    }
  }

  backtrack([], new Array(nums.length).fill(false));
  return result;
}

Q2: 全排列和组合有什么区别？​

答案：

排列组合
顺序[1,2] ≠ [2,1][1,2] = [2,1]
代码区别从 0 开始遍历 + used 数组从 start 开始遍历
数量Ank=n!(n−k)!A_n^k = \frac{n!}{(n-k)!}Cnk=n!k!(n−k)!C_n^k = \frac{n!}{k!(n-k)!}

Q3: 如何用非递归方式生成下一个排列？(LeetCode 31)​

答案：

function nextPermutation(nums: number[]): void {
  const n = nums.length;
  let i = n - 2;

  // 1. 从右往左找第一个 nums[i] < nums[i+1]
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;

  if (i >= 0) {
    // 2. 从右往左找第一个 nums[j] > nums[i]
    let j = n - 1;
    while (nums[j] <= nums[i]) j--;
    // 3. 交换
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  // 4. 反转 i+1 之后的部分
  let left = i + 1, right = n - 1;
  while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
    left++;
    right--;
  }
}

Q4: 时间复杂度为什么是 O(n × n!)？​

答案：

  • n! 是排列的总数（固定的，无法优化）
  • 每个排列需要 O(n)O(n) 时间来复制到结果数组
  • 所以总时间是 O(n×n!)O(n \times n!)
  • 对于 n=10n = 10，n!=3628800n! = 3628800，已经很大了；n=20n = 20 就完全不可行了

相关链接​