90-subsets-ii.md

90. 子集 II - medium

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

 

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

 

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

Solutions

1. 迭代

这是 78. 子集 升级版本，复杂在于有重复数据。对数组先做一次排序。然后同样使用 2 进制枚举，当 nums[i] == [nums][i-1] 且 i-1 不选取的时候，结果一定是和只选 i-1 一样的。所以这种情况直接跳过。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
  
        results = []
        n = len(nums)
        for mask in range(1 << n):
            vs = []
            skip = False
            for i in range(n):
                if mask >> i & 1:
                    if i > 0 and mask >> (i - 1) & 1 == 0 and nums[i] == nums[i - 1]:
                        skip = True
                        break
                    vs.append(nums[i])
            if not skip:
                results.append(vs)
        return results