LeetCode 「中等」46.全排列

全排列open in new window

题目描述

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

示例

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

输入：nums = [0,1]
输出：[[0,1],[1,0]]

输入：nums = [1]
输出：[[1]]

解答

回溯法

1. 定义问的解空间

对于数组 [1, 2, 3]，解空间是它的所有可能排列：

[
  [1, 2, 3],
  [1, 3, 2],
  [2, 1, 3],
  [2, 3, 1],
  [3, 1, 2],
  [3, 2, 1],
]

2. 递归构建解

• 初始状态：path = []，options = [1, 2, 3]
• 选择第一个数字 1，加入 path，path = [1]，options = [2, 3]
• 递归调用，选择第二个数字 2，path = [1, 2]，options = [3]
• 递归调用，选择第三个数字 3，path = [1, 2, 3]，options = []
• 此时 path 的长度等于数组的常读，找到一个解 [1, 2, 3]，加入结果集合

3. 回溯

• 回溯到上一步，撤销选择 3，path = [1, 2]，options = [3]
• 由于 options 中没有其他数字可选，继续回溯到上一步，撤销选择 2,path = [1]，options = [2, 3]
• 选择下一个数字 3，path = [1, 3]，options = [2]
• 继续递归，选择 2，path = [1, 3, 2]，找到另一个解

4. 重复上述过程

通过不断选择、递归和回溯，最终找到所有可能的排列

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
  const ans = [];

  const backtrack = (path, options) => {
    if (path.length === nums.length) {
      ans.push([...path]);
      return;
    }

    for (let i = 0; i < options.length; ++i) {
      path.push(options[i]);
      const newOptions = options.slice(0, i).concat(options.slice(i + 1));
      backtrack(path, newOptions);
      path.pop(); // 回溯
    }
  };

  backtrack([], nums);

  return ans;
};