回溯 + 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] 的全排列。

思路解析

• 按顺序枚举每一位可能出现的情况，已经选择的数字在 当前 要选择的数字中不能出现（设置一个 visited 数组）。

• 这样的思路，可以用一个树形结构表示。而树上的每一个结点表示了求解全排列问题的不同的阶段，这些阶段通过变量的「不同的值」体现，这些变量的不同的值，称之为「状态」；

• 使用深度优先遍历有「回头」的过程，在「回头」以后， 状态变量需要设置成为和先前一样 ，因此在回到上一层结点的过程中，需要撤销上一次的选择，这个操作称之为「状态重置」；

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

要注意的地方

• 要注意遍历到相应的结点的时候，状态变量的值是正确的，具体的做法是：往下走一层的时候，path 变量在尾部追加，而往回走的时候，需要撤销上一次的选择，也是在尾部操作，因此 path 变量是一个栈；
• 深度优先遍历通过「回溯」操作，实现了全局使用一份状态变量的效果(因此，在每次遍历到叶子结点要将 path 数组拷贝到 result 返回数组，即 new 一个，或 [...push])

代码解释

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

复制
1/**
2 * @param {number[]} nums
3 * @return {number[][]}
4 */
5var permute = function(nums) {
6    let len = nums.length, result = [], visited = new Array(len).fill(false);
7
8    const dfs = (nums, len, depth, path, visited) => {
9        // 遍历到叶子结点了，可以返回了
10        if(depth === len) {
11            result.push([...path]);
12        }
13
14        for(let i = 0; i < len; i++) {
15            // 如果没遍历过
16            if(!visited[i]) {
17                // 压入 path 数组，然后是否遍历过的数组此下标处变为 true
18                path.push(nums[i]);
19                visited[i] = true;
20                // 继续 dfs，直到最后一层
21                dfs(nums, len, depth + 1, path, visited);
22                // 进行回溯，还原，以便下一次使用
23                visited[i] = false;
24                path.pop();
25            }
26        }
27    }
28
29    dfs(nums, len, 0, [], visited);
30    return result;
31};