算法题--列出集合的所有子集

image.png

0. 链接

题目链接

1. 题目

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

2. 思路1：迭代法

• 先计算出每个数字的出现次数
• 对于不重复数字, 逐个迭代，并添加到结果列表里
• 每次迭代一个数字时，都在前面已经得出的结果列表的基础上，新增若干个(1~count)数字组成新列表，添加到结果中
• 等将所有不重复数字都迭代一遍后，将得到所有可能的子集

3. 代码

# coding:utf8
from typing import List
from collections import defaultdict


class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        # 先统计每个元素的出现次数
        num_dict = defaultdict(int)
        for num in nums:
            num_dict[num] += 1

        # 迭代的收集结果列表
        rtn_list = [[]]
        for num, count in num_dict.items():
            before_size = len(rtn_list)
            for i in range(before_size):
                for freq in range(1, count + 1):
                    rtn_list.append(rtn_list[i] + [num] * freq)

        return rtn_list


def my_test(solution, nums):
    print('input: nums={}; output: {}'.format(nums, solution.subsetsWithDup(nums)))


solution = Solution()
my_test(solution, [1, 2, 2])
my_test(solution, [0])

输出结果

input: nums=[1, 2, 2]; output: [[], [1], [2], [2, 2], [1, 2], [1, 2, 2]]
input: nums=[0]; output: [[], [0]]

4. 结果

image.png