題目描述

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]
]

難點(diǎn)

這個(gè)題的難點(diǎn)和subsets ii 基本一樣，就是如何去重
原則就是在使用2（2）時(shí)， 2（1）必然已經(jīng)使用了

解決辦法：

利用一個(gè)used數(shù)組記錄數(shù)字的使用情況
當(dāng)遇到2（2）時(shí)，如果2（1）使用過了，就可以用
否則，跳過這個(gè)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]:  # 因?yàn)?（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