@janos Answer is great, but it was easier for me to think about it with one less bitwise operations.
def subsets(s):
"""
:type s: list[]
"""
sets = []
for i in range(2**len(s)):
subset = []
for j in range(len(s)):
if i & (1 << j) > 0:
subset.append(s[j])
sets.append(subset)
return sets
Explanation:
So we know there are \$2^n\$ subsets in a set where \$n\$ is the size of the set. So we loop through all those numbers: for i in range(2**len(s)):
.
This gives us a range \$0 - 2^n\$ which corresponds to these binary numbers (example of a set of size 3):
0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110
7 = 111
...
n - 1 = 0b(n-1)
As you can see, the binary representation is every subset possible where 1 means it is in the set and 0 means it is not.
Now we just need to use these indexes to find out what should be in each set.
(While under the hood the numbers are stored as binary, if you try printing them you'll see an int.)
So we'll do a nested for loop: for j in range(len(s)):
Here we do need to do a bitwise operation: i & (1 << j) > 0
where i
is the current index of the loop described earlier. j
is the index of which element in the second loop we're at.
1 << j
just converts the index to the binary representation. For example, the first element (at index 0): 1 << 0 = 001
, or the second 1 << 1 = 010
, etc.
The &
operator just makes sure the indexes match up. 000 & 101 = 0
but 100 & 101 = 100
. So anytime it is greater than 0, it means we've come across an element that belongs in our set.
Let's take the set {a, b, c}
and loop through our range. At 0, 0 & anything = 0
, so we have the empty set.
Let's skip to i = 6: 6 & (1 << 0) > 0
returns false because in binary: 110 & 001 = 0
. But the second iteration (j = 1) 6 & (1 << 1) > 0
returns true (110 & 010 = 1
). And it will for the 3rd element too. Thus giving you the subset {b, c}.
The runtime of this algorithm is \$O(2^n)\$ if that isn't clear! Hope this helps!