16. 带重复元素的排列

class Solution:
    """
    @param: :  A list of integers
    @return: A list of unique permutations
    """

    def permuteUnique(self, nums):
        # write your code here
        #for循环内嵌dfs写法
        if not nums: return [[]]
        
        results = []
        visted = {}
        self.dfs(results, nums, [], 0, visted)
        
        return results
    
    def dfs(self, results, nums, array, index, visted):
        #递归的出口
        if (len(array) == len(nums)):
            if (array not in results):
                results.append(list(array))
            return
        
        #递归的拆解
        for i in range(len(nums)):
            if (i not in visted):
                visted[i] = True
                array.append(nums[i])
                self.dfs(results, nums, array, index + 1, visted)
                array.pop()
                visted.pop(i)