12. 全排列II（47）

一、题目内容 中等

给定一个可包含重复数字的序列 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 有重复元素。
这个时候我们去重，需要考虑两点：

1. 纵向遍历时，不能使用使用过的元素
2. 横向遍历时，同层不同支不能使用相同的元素

三、具体代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  nums.sort((a, b) => a - b)
  const res = []
  const path = []
  const used = [] // used[i] 中，i 代表 nums 的值的下标。used[i] 为 false 代表纵向遍历，true 代表横向遍历
  const backTracking = () => {
    if (path.length === nums.length) {
      res.push(path.map(i => i))
      return
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i - 1] === true && nums[i] === nums[i - 1]) continue // 排除了同层不同支，元素相同的情况下，继续递归
      if (used[i] === false) continue // 除去深度遍历中，使用相同的元素，即 path 中已经使用的
      used[i] = false
      path.push(nums[i])
      backTracking()
      path.pop()
      used[i] = true
    }
  }
  backTracking()
  return res
};

四、其他解法