Description

sl1673495

opened on Jun 11, 2020

Issue body actions

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

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

本题和全排列-46 的思路是一样的，只是在每次递归保存的时候，利用 Set 去重的特性，把每个值用字符串拼接的方式丢进 set 里去重，最后再处理成题目需要的格式即可。

let uniqSymbol = 'X'

let permuteUnique = function (nums) {
  let n = nums.length
  if (n === 1) {
    return [nums]
  }
  let permuteSet = (nums) => {
    let n = nums.length
    if (n === 0) {
      return new Set()
    }
    if (n === 1) {
      return new Set(nums)
    }

    let res = new Set()
    for (let i = 0; i < n; i++) {
      let use = nums[i]
      if (use === undefined) {
        continue
      }
      let rest = nums.slice(0, i).concat(nums.slice(i + 1, n))
      let restPermuteds = permuteSet(rest)
      restPermuteds.forEach((restPermuted) => {
        res.add(`${use}${uniqSymbol}${restPermuted}`)
      })
    }

    return res
  }

  let permuted = permuteSet(nums)

  return Array.from(permuted).map((val) => val.split(uniqSymbol).map(Number))
}

Activity

1. sl1673495

   added

   递归与回溯

   on Jun 11, 2020
2. vortesnail commented on Aug 14, 2021

   

   vortesnail

   on Aug 14, 2021

   More actions

   和 全排列 思路一样的回溯法，不过要在回溯过程中增加判断去重，一开始要先排好序：

   var permuteUnique = function (nums) {
     const res = [];
     const len = nums.length;
     // 先排序，目的是为了把重复的数字放到一起形成连续，便于后面判断
     nums.sort((a, b) => a - b);
   
     var backtracking = function (used, path) {
       if (path.length === len) {
         res.push([...path]);
       }
       for (let i = 0; i < len; i++) {
         if (used[i]) continue;
         // 现在假如 第二个数字也是 1，和第一个 1 重复了：
         // 1.首先下标肯定要大于等于 0
         // 2.前后数字相等
         // 3.前面的数字必须标记为 使用过了 ，如果没有这个判断，后面的逻辑都到不了，仔细想想就知道了。
         if (i - 1 >= 0 && nums[i - 1] === nums[i] && !used[i - 1]) continue;
   
         path.push(nums[i]);
         used[i] = true;
         backtracking(used, path);
         path.pop();
         used[i] = false;
       }
     }
   
     backtracking([], []);
     return res;
   };

Issue actions