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

  1. 输入：nums = [1,1,2]
  2. 输出：
  3. [[1,1,2],
  4.  [1,2,1],
  5.  [2,1,1]]

示例 2：

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

提示：

  • 1 <= nums.length <= 8

  • -10 <= nums[i] <= 10

    解法一：回溯

    1. function permuteUnique(nums: number[]): number[][] {
    2.   let res : Array<Array<number>> = []
    3.   nums.sort((a,b) => a-b)
    4.   let n = nums.length
    5.   let used = Array(n).fill(false)
    7.   recursion([])
    8.   return res
    10.   function recursion(cur :Array<number>) {
    11.       if(cur.length === n) {
    12.           res.push([...cur])
    13.           return
    14.       }
    15.       for (let [i, num] of nums.entries()) {
    16.           if (used[i]) {
    17.               continue
    18.           }
    19.           // 这里的剪枝条件需要增加前一个已经使用的
    20.           // 如果当前和前一个一样，那么存在两种情况，
    21.           // 一种是前一个已经使用了,那么当前可以正常使用，
    22.           // 如果前一个没使用,表示其已经进入到使用之后的逻辑了，所以当前这个不能用
    23.           if (i > 0 && num === nums[i-1] && !used[i-1]) {
    24.               continue
    25.           }
    26.           cur.push(num)
    27.           used[i] = true
    28.           recursion(cur)
    29.           cur.pop()
    30.           used[i] = false
    31.       }
    32.   }
    33. }