Permutations ii

题目描述

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