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

[chencl1986]

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

解题思路：

该题是47. 全排列 II的进阶版，在其之上加入了过滤出不重复排列的需求。如果你对47. 全排列 II的解法不熟悉，可以查看我的题解LeetCode题解：46. 全排列，回溯，JavaScript，详细注释。

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所有被使用过的状态都被清除，不会影响当前的递归。
4. 过滤重复排列的注意点：
   • 将nums进行排序，保证每个数字的连续性，一个数字判断完成之后不会重复判断。
   • 在递归中遍历数字时，以[1, 1, 2]为例，只有在遍历到第二个1时，才会采用其对应的排列，之前的排列全部都会被过滤掉。
5. 递归终止时，由于permutation只是一个引用，即它的值会随着函数的运行不断改变，因此需要将其copy一份，否则最终输出的结果都会是[]

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] || // 如果当前值已被排列过
      // 由于nums的值可重复，即使used[i]为false，当前值也有可能已被排列过
      // 如果相邻两个字相等，表示当前值可能已在前一个值的递归中被排列过
      (nums[i] === nums[i - 1] && used[i - 1]) // 判断前一个值是否已被排列过
    ) {
      continue;
    }
    // 当前值已经进行排列，在used中进行标识
    used[i] = true;
    // 将当前值存入排列
    permutation.push(nums[i]);
    // 可以在此处打印当前排列情况，帮助理解
    // console.log(result, permutation, used);

    // 3. 下探到下一层递归
    // 注意此时为深度优先遍历，也就是说recursion完成之后，已经处理完了一种排列的最终结果
    recursion(nums, result, permutation, used);

    // 4. 恢复当前层状态
    // 在当前值被使用过后，将used置为空，提供给下一次for循环使用
    used[i] = false;
    // 将当前已使用的值从permutation中弹出，避免英下乡下一次循环结果
    permutation.pop();
  }
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  let result = []; // 存储结果
  let permutation = []; // 存储每次排列的结果
  let used = new Array(nums.length).fill(false); // 通过index对应的布尔值，标识nums中各个值是否被使用
  nums.sort((a, b) => a - b); // 将nums进行排序，保证能否正确去重

  // 递归生成全排列
  recursion(nums, result, permutation, used);
  return result;
};