Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
这题是Permutations的一个拓展，主要是当原数组有重复元素的时候，如果依然按permutations的做法，则会产生重复的排列。比如［1，1，2］的数字，如果首先选择了第一个1，然后是第二个1，再是2和先选择第2个1，再选择第二个1，然后再选择2的结果是一样的。必然产生重复。所以对于这种情况，需要进行重复排除。首先输入的数组不一定有序，如果无序，先进行排序，之后在每一步的选择中，只选择重复数字的第一个数字作为一步，后面的一样的数字则不做操作。避免上述的重复情况。代码相比permutation的代码只需要增加一行，如下：
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums:
return [[]]
nums.sort()
allPer = []
per = []
used = [False] * len(nums)
self.helper(nums, used, per, allPer)
return allPer
def helper(self, nums, used, per, allPer):
if len(per) == len(nums):
allPer.append(per+[])
return
for i in xrange(len(nums)):
if used[i]: continue
if i > 0 and nums[i] == nums[i-1] and not used[i-1]: ＃排除重复，对于每一步只取重复元素中的第一个。
continue
per.append(nums[i])
used[i] = True
self.helper(nums, used, per, allPer)
per.pop()
used[i] = False
转载于:https://www.cnblogs.com/sherylwang/p/5567096.html
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
