# Computing the powerset

#### Posted on March 6, 2013

##### Last updated on March 6, 2013

Problem Statement:

Generate the power set of a set $$S$$ of $$n$$ elements.

This is also a nice, short, and quick interview question. Straight away we know that our algorithm will be exponential, $$O(2^n)$$ since that’s the size of the powerset.

We can easily think about this recursively. The power set of the empty set is a set with one element, the empty set. The empty set is part of the powerset of any set. Then, think of an element $$x_i$$ from $$S$$. Assuming we have the solution for the powerset $$P_1$$ of $$S - \{x_i\}$$ }, we can put $$x_i$$ into every element of that set, and take the union of it with $$P_1$$:

Translating this into simple code is as follows. In the code, $$i$$ is the index from which we want the to take the powerset of $$S$$. We get the whole powerset of $$S$$ when $$i=0$$.

Testing it with a simple example…

This confirms the code is correct.

Markdown SHA1: dd52ec248a41d10e228b449f756c3c689ca8834e