一种容易理解的生成集合(含重复)的所有子集的方法

Posted by daquexian on January 23, 2017

从LeetCode的讨论区看到的,这里

    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        i = 0
        res = [[]]
        while i < len(nums):
            n = 1
            while i + 1 < len(nums) and nums[i] == nums[i + 1]:
                i, n = i + 1, n + 1
            new_list = []
            for j in range(n):
                new_list.extend([x + (j + 1) * [nums[i]] for x in res])
            res.extend(new_list)
            i += 1
        return res
    

大致思路是,对出现k次的元素,将已有的子集集合中的复制k份,每份中的每个子集分别添加i个该元素(1 <= i <= k),并到原子集集合中。

这个方法容易理解,正因为如此应该适合记住然后到面试什么的时候用吧,不过缺陷是生成的幂集中的子集的排列是比较无序的,不知道有没有题目会在意这一点。