【LeetCode】0090 子集II

https://leetcode-cn.com/problems/subsets-ii/

# -*- coding:utf-8 -*-
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        dic = {}
        for i in nums:
            dic[i] = dic.get(i, 0) + 1
        res = [[]]
        for i, v in dic.items():
            temp = res.copy()
            for j in res:
                temp.extend(j + [i] * (k + 1) for k in range(v))
            res = temp
        return res
if __name__ == '__main__':
    nums = [1, 2, 2]
    print(Solution().subsetsWithDup(nums))

思路：这道题的第一眼就看出来是回溯，题不是难题，但是学到了一个比较新颖的解题思路，那就是先统计所有数字出现的次数，存到一个字典里，然后依次遍历这个字典，将每个数字加到结果的后面。

比如当前结果有[]何[1]，我们在nums中统计到了2个2，因此我们添加[2],[1,2]和[2,2],[1,2,2]，即是当前情况下的子集。