Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]
给定一组可能有重复元素不同的整数，返回所有可能的排列（不能包含重复）。
- 此问题同46题思路，条件基本一致，只是给定的数组中可能有重复值，需要去掉.
- 假设数组A[10],我们在遍历每个元素A[i]的时候，都检查A[i]是否在A[1:i]中出现过，如果曾经出现，则直接跳过
class Solution:
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
# 递归返回条件：只有一个值，直接返回
if len(nums) == 1:
return [nums]
# 声明最终需要返回的答案
res = []
# 遍历数组中的元素
for i, num in enumerate(nums):
# 检查元素是否已经出现过，若是，则直接进入下一层循环
if i != 0 and num in nums[0:i]:
continue
# 去掉已经遍历的元素
subnum = nums[:i]+nums[i+1:]
# 去掉元素nums[i],假设子问题subnum的所有组合已经拿到，把num[i]和所有可能的组合相加，得到结果
for subres in self.permuteUnique(subnum):
res.append([num]+subres)
return res