难度: Medium
给定一个可包含重复数字的整数集合 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]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10注意：本题与主站 47 题相同： https://leetcode-cn.com/problems/permutations-ii/
运行时间: 34 ms
内存: 16.3 MB
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
def backtrack(i):
if i == len(nums):
# print(nums)
ans.append(nums[:])
return
used = set()
for j in range(i, len(nums)):
if nums[j] in used:
continue
used.add(nums[j])
nums[i], nums[j] = nums[j], nums[i]
backtrack(i+1)
nums[i], nums[j] = nums[j], nums[i]
backtrack(0)
return ans
题解采用了回溯法来生成不重复的全排列。首先，将数组排序以方便后续步骤中的去重处理。定义一个递归函数 `backtrack(i)`，其中 `i` 表示当前固定元素的位置。在每次调用 `backtrack` 时，如果 `i` 等于数组长度，说明找到了一个全排列，将其添加到结果列表 `ans` 中。否则，使用一个集合 `used` 来记录在当前位置 `i` 已经尝试过的元素值，以避免生成重复的排列。对于每个从 `i` 到数组末尾的位置 `j`，如果该位置上的元素未被使用过，则将其与位置 `i` 的元素交换，并递归调用 `backtrack(i+1)`，完成更深层次的排列生成。递归完成后，再将元素交换回来，以便进行下一次的排列尝试。
时间复杂度: O(n * n!)
空间复杂度: O(n * n!)
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort() # 对数组进行排序，以便去重
ans = []
def backtrack(i):
if i == len(nums):
# 当全部元素都固定在位置后，将当前排列复制到结果列表
ans.append(nums[:])
return
used = set() # 用来记录在当前位置尝试过的元素
for j in range(i, len(nums)):
if nums[j] in used:
continue # 如果当前元素已经尝试过，跳过以避免重复
used.add(nums[j])
nums[i], nums[j] = nums[j], nums[i] # 交换元素
backtrack(i+1) # 递归调用，进入下一层递归
nums[i], nums[j] = nums[j], nums[i] # 撤销交换，尝试下一个可能的元素
backtrack(0)
return ans
在实现'全排列 II'时，先对数组进行排序是为了方便后续步骤中有效地去除重复的排列。排序后，相同的数字会被排列在一起，这使得在递归过程中，可以通过比较连续的元素来简单地检查和避免重复的排列。如果数组未排序，相同的元素可能分散在数组中不同的位置，这将使得去重的过程变得复杂和低效。因此，排序是为了让重复元素彼此相邻，从而在使用集合`used`记录和检查已尝试过的元素时，能够简单快速地判断和跳过重复的元素，确保生成的全排列是唯一的。
在递归生成全排列的过程中，集合`used`的作用是记录在当前递归层级（即在数组的特定位置`i`）已经尝试过的元素值。通过这种方式，即使数组中有重复的元素，我们也可以防止在同一层递归中重复使用相同的元素生成排列。具体来说，对于每个从`i`到数组末尾的位置`j`，在尝试将位置`j`的元素与位置`i`的元素交换之前，我们首先检查该元素是否已存在于`used`集合中。如果存在，我们跳过该元素，继续检查下一个元素。这种方法确保每个元素在每个位置只被尝试一次，从而有效防止重复的排列生成。这种机制非常依赖于数组事先已经被排序，使得相同的元素聚集在一起，以便`used`集合能有效地工作。
在递归函数`backtrack(i)`中，当`i`等于数组`nums`的长度时，意味着一个全排列已经形成。这里使用`nums[:]`而不是直接使用`nums`，是因为`nums[:]`创建了`nums`的一个浅拷贝，即它复制了数组中所有的元素生成一个新的列表。这是必要的，因为数组`nums`在递归过程中会不断地被修改（元素交换），直接使用原数组`nums`将导致结果列表`ans`中所有的子列表都指向同一个数组实例，这个实例的内容在每次递归调用后都可能改变。因此，使用`nums[:]`确保每一个全排列都被正确地保存下来，而不会因为后续的递归调用而被修改。