LeetCode 题解：46. 全排列，回溯，JavaScript，详细注释

原题链接：https://leetcode-cn.com/problems/permutations/

解题思路：

可以先参考官方题解中的视频讲解。

1. 使用DFS生成所有可能的排列情况。

2. 需要使用 used 数组，标识 nums 中每个值是否被使用过。

3. 清除状态的注意点：

* 由于 permutation 和 used 变量会在每次递归被重复使用，需要注意每次递归后恢复当前状态。

* 假设是第一层递归，for 循环清除状态后每次得到的 permutation 分别为[1]、[2]、 [3]， used 分别为[true, false, false]、[false, true, false]、[false, false, true]。

* 也就是说，当 permutation 为[2]时，上一次循环中所有可能的排列情况都已被输出，而且 nums 所有被使用过的状态都被清除，不会影响当前的递归。

1. 递归终止时，由于 permutation 只是一个引用，即它的值会随着函数的运行不断改变，因此需要将其 copy 一份，否则最终输出的结果都会是[]
   

```javascript []

function recursion(nums, result, permutation, used) {

// 1. 递归终止条件

// 当排列的结果达到原序列长度时，退出循环

if (permutation.length === nums.length) {

// 将当前排列存入结果，需要将原数组 copy 一份，否则 permutation 会在 for 循环结束后被清空

result.push(permutation.slice());

return;

}

// 利用循环产生不同的排列

// 假设是第一层递归，for 循环每次得到的 permutation 分别为[1], [2], [3]。

// 下一层的递归就在第一层的基础上继续进行

// 由于进入每一层递归时，并不知道上一层的排列情况，只能进行遍历查找。

for (let i = 0; i < nums.length; i++) {

// 2. 当前层的递归逻辑

// 如果当前值已经被使用过，则不可以进行排列，直接跳过

if (used[i]) {

continue;

}

// 当前值已经进行排列，在 used 中进行标识

used[i] = true;

// 将当前值存入排列

permutation.push(nums[i]);

// 3. 下探到下一层递归

// 注意此时为深度优先遍历，也就是说 recursion 完成之后，已经处理完了一种排列的最终结果

recursion(nums, result, permutation, used);

// 4. 恢复当前层状态

// 在当前值被使用过后，将 used 置为空，提供给下一次 for 循环使用

used[i] = false;

// 将当前已使用的值从 permutation 中弹出，避免英下乡下一次循环结果

permutation.pop();

}

}

/**

* @param {number[]} nums

* @return {number[][]}

*/

var permute = function (nums) {

let result = []; // 存储结果

let permutation = []; // 存储每次排列的结果

let used = new Array(nums.length).fill(false); // 通过 index 对应的布尔值，标识 nums 中各个值是否被使用

// 递归生成全排列

recursion(nums, result, permutation, used);

return result;

};

```