permutations ii (全排列有重复的元素)

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        nums.sort()
        if len(nums)==1:
            return [nums]
        n = len(nums)
        # print(n)
        nums = ['a']+nums
        a = [0]*(n+1)
        book = [0]*(n+1)
        
        ret = []
        
        def dfs(step):
            if step==n+1:
                ret.append(a[1:])

            for i in range(1,n+1):

                if i>1 and nums[i]==nums[i-1] and book[i-1]==0:
                    continue

                if book[i]==0:
                    a[step] = nums[i]
                    book[i] = 1

                    dfs(step+1)
                    book[i] = 0
            return
        
        dfs(1)
        return ret