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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def permuteUnique(self , num: List[int]) -> List[List[int]]:
        # write code here
        res = []
        temp = []
        has_used = [False] * len(num)  # has_used既用于树层去重，也用于path去重
        def huisu():
            if len(temp) == len(num):
                res.append(temp[:])
                return
            for i in range(len(num)):
                if has_used[i]:
                    continue
                if i > 0 and num[i] == num[i-1] and not has_used[i-1]:
                    continue
                # 去重详细解释见https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html#%E5%9B%9E%E6%BA%AF%E4%B8%89%E9%83%A8%E6%9B%B2
                temp.append(num[i])
                has_used[i] = True
                huisu()
                temp.pop()
                has_used[i] = False
        num.sort()
        huisu()
        return res