学习记录：js算法（八十六）：全排列 II

全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

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

思路一

function permuteUnique(nums) {
  nums.sort((a, b) => a - b); // 1. 排序以避免重复

  const results = []; //  存储结果

  const backtrack = (path, options) => { // 2. 递归函数
    if (options.length === 0) { // 3. 基本结束条件
      results.push(path);
      return;
    }

    for (let i = 0; i < options.length; i++) {
      // 4. 回溯过程: 跳过重复元素
      if (i > 0 && options[i] === options[i - 1]) continue;

      const newPath = [...path, options[i]]; // 5.1 添加到路径
      const newOptions = [...options.slice(0, i), ...options.slice(i + 1)]; // 5.2 移除当前数字

      backtrack(newPath, newOptions); // 5.3 递归调用
    }
  };

  backtrack([], nums); // 5. 开始回溯

  return results; // 6. 返回结果
}

讲解
我们需要找到所有不重复的全排列，考虑到序列中可能包含重复的数字，我们需要在递归过程中避免生成重复的排列。

1. 排序：首先对输入数组 nums 进行排序。这样可以帮助我们在递归过程中跳过重复的元素。
2. 递归函数:
   ○ 定义一个递归函数 backtrack，它接受两个参数：
   ■ path: 当前正在构建的排列。
   ■ options: 剩余可选数字的集合。
3. 基本结束条件:
   ○ 如果 options 集合为空，这意味着我们已经选择了一个全排列。
   ○ 此时将当前路径 path 加入结果数组 results，然后返回。
4. 回溯过程:
   ○ 对于 options 集合中的每一个数字，执行以下操作：
   ■ 如果当前数字与前一个数字相同（且前一个数字已经被考虑过），则跳过当前数字以避免重复。
   ■ 将当前数字添加到路径 path 中。
   ■ 从 options 集合中移除当前数字。
   ■ 递归调用 backtrack 函数，传递更新后的 path 和 options。
   ■ 回溯，即将当前数字从路径 path 中移除。
5. 开始回溯:
   ○ 调用 backtrack 函数，传入初始的 path 和 options（即 nums）。
6. 返回结果:
   ○ 使用一个数组来存储所有不重复的全排列。最后返回结果数组 results。