题目描述
Given a list of numbers with duplicate number in it. Find all unique permutations.
Example
For numbers [1,2,2] the unique permutations are:
[
[1,2,2],
[2,1,2],
[2,2,1]
]
难点
这个题的难点和subsets ii 基本一样，就是如何去重
原则就是在使用2（2）时， 2（1）必然已经使用了
解决办法：
利用一个used数组记录数字的使用情况
当遇到2（2）时，如果2（1）使用过了，就可以用
否则，跳过这个2（2）
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums:
return [[]]
nums.sort() # sort
self. result = []
used = [0] * len(nums)
self.dfs(nums, used, [])
return self.result
def dfs(self, nums, used, path):
if len(nums) == len(path):
self.result.append(list(path))
return
for i in range(len(nums)):
if i != 0 and nums[i] == nums[i-1]: # 遇到2（2）
if not used[i-1]: # 因为2（1）没有使用，所以跳过2（2）
continue
if not used[i]:
used[i] = 1
path.append(nums[i])
self.dfs(nums, used, path)
path.pop()
used[i] = 0
