请先做前置题目「NC43 没有重复项数字的全排列」。

本题和上一题的区别是数组中“存在重复元素”。当数组存在重复元素时，排列方案中也存在重复的排列方案。

为了排除这些重复方案，需在固定某位元素时，保证“每种元素只在此位固定一次”，即遇到重复元素时不交换，直接跳过，从而将生成重复排列的搜索分支进行“剪枝” 。

递归解析：

  1. 终止条件： 当 x = len(nums) - 1 时，代表所有位已固定（最后一位只有 1 种情况），则将当前组合 nums 转化为数组并加入 res ，并返回。
  2. 递推参数： 当前固定位 x 。
  3. 递推工作： 初始化一个 Set ，用于排除重复的元素；将第 x 位元素与 i ∈ [x, len(nums)] 元素分别交换，并进入下层递归。
  4. 剪枝： 若 nums[i] 在 Set​ 中，代表其是重复元素，因此 “剪枝” 。
  5. 将 nums[i] 加入 Set​ ，以便之后遇到重复元素时剪枝。
  6. 固定元素： 将元素 nums[i] 和 nums[x] 交换，即固定 nums[i] 为当前位元素。
  7. 开启下层递归： 调用 dfs(x + 1) ，即开始固定第 x + 1 个元素。
  8. 还原交换： 将元素 nums[i] 和 nums[x] 交换（还原之前的交换）。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param num int整型一维数组
# @return int整型二维数组
#
class Solution:
    def permuteUnique(self, num: List[int]) -> List[List[int]]:
        # write code here
        def dfs(x):
            if x == len(num) - 1:
                ans.append(num[:])  # 添加排列方案
                return
            dic = set()
            for i in range(x, len(num)):
                if num[i] in dic:
                    continue  # 重复，因此剪枝
                dic.add(num[i])
                num[i], num[x] = num[x], num[i]  # 交换，将 nums[i] 固定在第 x 位
                dfs(x + 1)  # 开启固定第 x + 1 位元素
                num[i], num[x] = num[x], num[i]  # 恢复交换

        ans = []
        dfs(0)
        return sorted(ans) # 注意排序，否则提交可能不通过