题解 | #有重复项数字的全排列#

class Solution:  
    def permuteUnique(self, num: List[int]) -> List[List[int]]:  
        def backtrack(first):  
            if first == n:  
                output.append(num[:])  
                return  
            used = set()  
            for i in range(first, n):  
                # 如果当前数字已经被使用过，则跳过以避免重复排列  
                if num[i] in used:  
                    continue  
                used.add(num[i])  
                num[first], num[i] = num[i], num[first]  
                backtrack(first + 1)  
                num[first], num[i] = num[i], num[first]  
  
        n = len(num)  
        output = []  
        # 对数组进行排序，以确保结果以字典序升序排列  
        num.sort()  
        backtrack(0) 
        output.sort() # 如果笔试的时候，输入的结果不是按照字典顺序，那就直接排序，面试的话，是不是按字典排序的看不出来
        return output