Short and Clear Solutions


  • 2

    Straight-forward iterative solution:

    def subsets(self, nums):
        subsets = [[]]
        for n in nums:
            subsets += [s + [n] for s in subsets]
        return subsets
    

    Same thing but with reduce instead of the loop:

    def subsets(self, nums):
        return reduce(lambda subsets, n: subsets + [s+[n] for s in subsets], nums, [[]])
    

    Using combinations from the library:

    def subsets(self, nums):
        return [s for n in range(len(nums)+1)
                for s in itertools.combinations(nums, n)]
    

    Using integers as bit mask to tell which elements to use in a subset:

    def subsets(self, nums):
        return [[nums[i] for i in range(len(nums)) if mask >> i & 1]
                for mask in range(2 ** len(nums))]

  • 0

    Your usage of list comprehension is really clever :-)


  • 0
    J

    @StefanPochmann Hi StefanPochmann, your solutions are so clever. At the same time, would you please do me a favor by analyzing the time and space complexity of your first implementation (the iterative method)? Thank you very much in advance!


  • 0

    I have thought about using bit mask. Your bit solution is clear but it is also much slower than your other solutions. Could it be more efficient?

    N = 20, 0.25s for combinations solution.
    N = 20, 1s for reduce solution.
    N = 20, 0.7s for my product solution.

    def subsets(self, nums):
        return [filter(None, l) for l in itertools.product(*zip(nums, [None] * len(nums)))]
    

  • 2

    @lee215 A big reason why the combinations solution is so fast is that it returns a list of tuples instead of lists like it's supposed to. Turning them into lists makes that solution about as fast as the reduce solutions.

    I think the bit mask solution is so slow because I'm building every list from scratch element by element and in my own Python code. It's just much faster to add one element to an existing list. I don't think there's much one can do without significantly altering the solution. Here's one that's about as fast as the reduce solutions, though:

    def subsets(self, nums):
        n = len(nums)
        subsets = [[]] * 2**n
        for i in xrange(n):
            subsets[1 << i] = [nums[i]]
        for mask in xrange(1, 2**n):
            subsets[mask] = subsets[mask & -mask] + subsets[mask & mask-1]
        return subsets
    

    And here's one that's super fast, returns instantly because it's lazy:

    def subsets(self, nums):
        class FakeList(list):
            def __len__(self):
                return 2**len(nums)
            def __getitem__(self, mask):
                return [num for i, num in enumerate(nums) if mask >> i & 1]
        return FakeList()
    

    Btw, your solution is wrong and doesn't even get accepted. For input [0] you return [[],[]] instead of [[],[0]].


  • 0

    @StefanPochmann
    It was embarrassing. I correct it.

    def subsets(self, nums):
        return [filter(lambda x: x != None, l) for l in itertools.product(*zip(nums, [None] * len(nums)))]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.