给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

思路

看每个数字出现多少次，计算选择每个数字的次数的方案数
如 1,2,2,2,3,3
1:0,1； 2:0,1,2,3； 3:0,1,2

总方案数：2*4*3=24

import copy
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        self.ans = []
        self.path = []
        self.nums = sorted(nums)
        self.dfs(0)
        return self.ans 

    def dfs(self, u): # u表示当前子集元素个数，数组元素的索引
        print(u, self.path)
        if u == len(self.nums):
            self.ans.append(copy.copy(self.path))
            return None

        # 计算当前数字的个数
        k = 0
        while u + k < len(self.nums) and self.nums[u+k] == self.nums[u]:
            k += 1
        # k 为当前数字的出现次数

        for i in range(k+1):# 选择当前数字的次数为0,1,...,k-1,k，总共k+1种方案
            self.dfs(u + k) # 枚举下一个数，若i=0，此时当前数还没加入路径，相当于选0次当前数字
            self.path.append(copy.copy(self.nums[u])) 
            # 每次循环往路径加一次当前数，记得在dfs之后，否则漏掉选0次的情况

        # 恢复现场
        for i in range(k+1):
            self.path.pop()