Simp 5 line Python solution inspired by some math

  • 0
    def subsets(self, arr):
        length = len(arr)
        powerset = []
        for i in range(2**length):
            powerset.append([arr[j] for j in range(length) if i & 2**j])
        return powerset

    To explain the loop, each subset in the "powerset" (set of subsets) has a nice representation via the function:

    f(k) = 1 if the kth element of arr is in the subset and 0 otherwise.

    One can see that, collectively, the values [f(length-1), ..., f(1), f(0)] is just a binary representation of a number between 0 and 2^{length}-1. So iterating over all numbers between 0 and 2^{length}-1 and forming subsets this way, we get all the subsets.

    As an aside, it's using this subset f that one can show there's no 1-to-1 correspondence between elements of a set and its powerset (set of subsets). This is intimately linked to Russell's paradox, which shows a flaw in the naive formulation of set theory.

Log in to reply

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