题解采用了回溯法来生成不重复的全排列。首先,将数组排序以方便后续步骤中的去重处理。定义一个递归函数 `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