2^n complexity algorithm

Question

I need to implement and test an algorithm with a 2^n complexity. I have been trying to find one for a while. If there is any way I can acheive this by implementation -- with a exact complexity of 2^n that would be optimal. If anyone knows of a location I can find an example, or could help me implement one, that would be awesome :-). The basic operation can be anything, but a single statment like i++; would be best.

Answer 1

Generate all subsets of a set with n elements.

Added. The simplest way of generating all the subsets of S = {a0, a1, ..., an-1} is probably to translate between the binary representation of the rank and the subset.

Take S = {a0, a1, a2}.

rank binary subset
0    000    {} 
1    001    {a0}
2    010    {a1}
3    011    {a0, a1}
4    100    {a2}
5    101    {a0, a2}
6    110    {a1, a2}
7    111    {a0, a1, a2}

So, a 1 in the binary means the corresponding element is in the subset. A 0 means the element is not in the subset.

But you should also lookup Gray code.