全排列 II-47

[sl1673495]

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

示例:

输入: [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))
}

[vortesnail]

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

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;
};