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

还好，加个剪枝逻辑就好了。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def wuhu(self, output, added_list, remain_list):
        n = len(remain_list)
        if n == 0:
            output.append(added_list[:])
            return

        for i in range(n):
            # 剪枝操作：如果当前数字和前一个数字相同且前一个数字还未被使用，跳过
            if i > 0 and remain_list[i] == remain_list[i - 1]:
                continue
            new_added_list = added_list + [remain_list[i]]
            new_remain_list = remain_list[:i] + remain_list[i + 1:]
            self.wuhu(output, new_added_list, new_remain_list)

    def permuteUnique(self, num: List[int]) -> List[List[int]]:
        if not num:
            return []
        # 对输入列表进行排序
        num.sort()
        output, added_list, remain_list = [], [], num
        self.wuhu(output, added_list, remain_list)
        return output