Simp 5 line Python solution inspired by some math

• ``````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.

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