Power Set

Felix Lee
3 min readJul 3, 2022

--

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!

--

--

Felix Lee
Felix Lee

Written by Felix Lee

Software engineer in Singapore. Write random tech stuff. Still figuring out this “life” thing in life.

No responses yet