Programming Stuffs

Power Sets

For a given set of items, power set is the set of all subsets of it. If there are $n$ items in the given set, then there are $2^n$ subsets.

Generating Power Sets

One of the way to generate Power Sets is using binary numbers. For each of the set in the power sets, we have $two$ choices for an item in the given set - include it or not include it. This can be denoted as 1 and 0. We know that, if we have $n$ bits, then we can form $2^n$ numbers using a sequence $0$ and $1$ $n$ bits. Similarly, if have $n$ items set, then each of the binary number from $0$ to $2^n - 1$ will represent a sub set. If a bit is $ith$ bit is $0$, then the $ith$ item is excluded from the subset, else we include it.

Following picture should clearly explain this concept.

Implementation

Time Complexity

There are $2^n$ subsets. We can't avoid computation of each subset. Here in this method, to determine each subset, we traverse through each of the item. $\therefore$ The complexity of this approach is $\cal{O(n2^n)}$ which is exponential with the size of the input.

---

---

---