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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {

};

参考答案

回溯 + 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) 的时间复杂度判断这个数是否被选择过，这是一种「以空间换时间」的思想。
  • 这些变量称为「状态变量」，它们表示了在求解一个问题的时候所处的阶段。需要根据问题的场景设计合适的状态变量。
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let len = nums.length, result = [], visited = new Array(len).fill(false);

    const dfs = (nums, len, 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(nums, len, depth + 1, path, visited);
                // 进行回溯，还原，以便下一次使用
                visited[i] = false;
                path.pop();
            }
        }
    }

    dfs(nums, len, 0, [], visited);
    return result;
};