题目

题目来源：力扣（LeetCode）

给定一个可包含重复数字的序列 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]]

思路分析

回溯

  • 先对数组进行升序排序，以保证相同的数字相邻
  • 然后从左到右遍历数组，如果当前数字和前一个相同，即nums[i] == nums[i - 1],当前数字已经被选过，则直接跳过当前数字
  1. /**
  2. * @param {number[]} nums
  3. * @return {number[][]}
  4. */
  5. var permuteUnique = function (nums) {
  6.   let res = [];
  7.   let len = nums.length
  8.   // 对数组进行升序排序，保证相同的数字都相邻
  9.   nums.sort((a, b) => a - b)
  10.   unique([], 0)
  11.   return res
  13.   function unique(arr) {
  14.     // 个数选够了，将当前排列加入结果中
  15.     if (arr.length == len) {
  16.       res.push([...arr])
  17.       return
  18.     }
  20.     // 枚举出所有的选择
  21.     for (let i = 0; i < nums.length; i++) {
  22.       // 跳过，避免产生重复的排列
  23.       if (nums[i] == nums[i - 1]) continue 
  24.       // 将当前的数字加入排列中
  25.       arr.push(nums[i])
  26.       // 由于当前数字已经加入排列中，因此将当前数字从nums数组中删除
  27.       // 直接将当前已选择的数字从原数组中删除或重新加入，减少了额外定义变量来记录当前数字是否已被选择
  28.       nums.splice(i, 1)
  29.       // 基于已选的数字，递归继续选择未选的数字
  30.       unique(arr)
  32.       // 从 排列中撤销当前选择的数字，并将当前数字重新放回nums数组中，这一步是回溯
  33.       nums.splice(i, 0, arr.pop()) 
  34.     }
  35.   }
  36. };