A power set is a set of all subsets of a set, including empty set and the set itself.
Let’s look at a few examples to understand what that statement really means.
We are at the grocery store, we want to buy apple or banana:
{apple, banana}
- Empty -> {}
- Single item -> {apple}, {banana}
- Two items (everything) -> {apple, banana}
We get 4 subsets.
How about 3 items? Let’s add carrot to the item list.
{apple, banana, carrot}
- Empty (We don’t feel like buying anything)-> {}
- Single item -> {apple}, {banana}, {carrot}
- Two items -> {apple, banana}, {apple, carrot}, {banana, carrot}
- Three items (Give us everything!) -> {apple, banana, carrot}
If we have 3 items, we will get 8 subsets.
If we do it with 1 item, we will get 2 subsets — empty and 1 item(everything) subset. If we do it with 4 items, we will get 16 subsets!
Notice how each time we add 1 item to the set, we will get 2x of subsets that we can get. In another word, the power set of a set is 2 to the power of n, where n is the number of item in the set.
0 item -> 1 subset
1 item -> 2 subsets
2 items -> 4 subsets
3 items -> 8 subsets
4 items -> 16 subsets
5 items -> 32 subsets
If you are thinking, “hey, it’s binary!”, You are absolutely correct!
Binary
Here is a table to see how our items (a = apple, b = banana, c = carrot) can be mapped to a binary representation.
How do we solve this with code? Let’s think just for a bit.
First, we know that the number of subsets is 2^n. So let’s do that first.
Next, we just have to put in the item to the subset, but how? The hint is in the table above! We are looping from 0 to 2^n. If we have 3 items, we will loop from 0 to 7.
All we have to do is to check whether it is a 1(set bit) or 0(unset bit) at that bit for that number. If it is a 1, we add that item to the subset.
We can use an AND operator to help us for this. Basically, the bitwise AND operator (&) returns a 1 in each bit position if the corresponding bits of both binary numbers are 1s.
We get all 0 for our subset, we won’t be adding any item to the subset, thus we get an empty subset ({})
For the first loop of the inner loop, we get 1 for bit 2⁰, so we will add that item to the subset
You can continue to do this exercise and see everything falls into place.
Space and Time Complexity
Space complexity
We are storing 2^n items in the area, so the space complexity would be O(2^n)
Time complexity
The outer loop iterates 2^n times and the inner loop iterates n times, so the time complexity is O(n*(2^n))
Thanks for reading! You can also find me on LinkedIn (https://www.linkedin.com/in/yoongtilee/) if you want to connect!
