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的做法，则会产生重复的排列。比如［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