46. 全排列

解题思路

回溯 + DFS 思想

例子解析

先用 (1, 2, 3) 进行举例：

• 以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列；
• 以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；
• 以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。

思路解析

1. 按顺序枚举每一位可能出现的情况，已经选择的数字在当前要选择的数字中不能出现（设置一个 visited 数组）。
2. 这样的思路，可以用一个树形结构表示。而树上的每一个结点表示了求解全排列问题的不同的阶段，这些阶段通过变量的「不同的值」体现，这些变量的不同的值，称之为「状态」；
3. 使用深度优先遍历有「回头」的过程，在「回头」以后， 状态变量需要设置成为和先前一样 ，因此在回到上一层结点的过程中，需要撤销上一次的选择，这个操作称之为「状态重置」；

使用编程的方法得到全排列，就是在这样的一个树形结构中完成遍历，从树的根结点到叶子结点形成的路径就是其中一个全排列。

要注意的地方

• 要注意遍历到相应的结点的时候，状态变量的值是正确的，具体的做法是：往下走一层的时候，path 变量在尾部追加，而往回走的时候，需要撤销上一次的选择，也是在尾部操作，因此 path 变量是一个栈；

• 深度优先遍历通过「回溯」操作，实现了全局使用一份状态变量的效果(因此，在每次遍历到叶子结点要将 path 数组拷贝到 result 返回数组，即 new 一个，或 [...push])

代码解释

1. 首先这棵树除了根结点和叶子结点以外，每一个结点做的事情其实是一样的，即：在已经选择了一些数的前提下，在剩下的还没有选择的数中，依次选择一个数，这显然是一个 递归 结构；
2. 递归的终止条件是： 一个排列中的数字已经选够了 ，因此我们需要一个变量来表示当前程序递归到第几层，我们把这个变量叫做 depth。
3. 布尔数组 visited，初始化的时候都为 false 表示这些数还没有被选择，当我们选定一个数的时候，就将这个数组的相应位置设置为 true ，这样在进行下一层递归时，就能够以 O(1) 的时间复杂度判断这个数是否被选择过，这是一种「以空间换时间」的思想。
4. 这些变量称为「状态变量」，它们表示了在求解一个问题的时候所处的阶段。需要根据问题的场景设计合适的状态变量。

代码实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  let len = nums.length,
    result = [],
    visited = new Array(len).fill(false)

  const dfs = (depth, path, visited) => {
    // 遍历到叶子结点了，可以返回了
    if (depth === len) {
      result.push([...path])
    }

    for (let i = 0; i < len; i++) {
      // 如果没遍历过
      if (!visited[i]) {
        // 压入 path 数组，然后是否遍历过的数组此下标处变为 true
        path.push(nums[i])
        visited[i] = true
        // 继续 dfs，直到最后一层
        dfs(depth + 1, path, visited)
        // 进行回溯，还原，以便下一次使用
        visited[i] = false
        path.pop()
      }
    }
  }

  dfs(0, [], visited)
  return result
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const len = nums.length
  if (len === 1) {
    return [nums]
  }
  let map = new Map()
  map.set(1, [
    [nums[0], nums[1]],
    [nums[1], nums[0]],
  ])
  for (let i = 2; i < len; i++) {
    let result = []
    const lastResult = map.get(i - 1)
    lastResult.forEach((item) => {
      for (let j = 0; j <= i; j++) {
        const newItem = [...item]
        newItem.splice(j, 0, nums[i])
        result.push(newItem)
      }
    })
    map.set(i, result)
  }
  return map.get(len - 1)
}