Powerset Algorithm in C++

What is PowerSet?

A powerset of a given set is the combination of all subsets, including the empty subset and the set itself. Suppose we have the following set: {1,2,3}. Its powerset would be:

Creating an algorithm to generate a powerset is not trivial. The first idea you can use is to implement an iterative algorithm that uses a stack to grow and shrink the set as needed. The benefit of this approach is that it prints the subsets in lexicographic order. Below you’ll find an implementation in C++ that prints the powerset of the set 1,2,3… n (where you can specify n in the program):

The output for the set {1,2,3,4} is this:

You can also implement the powerset algorithm with recursion. The main recursive function would look like this (s is again the stack, k the position, m the starting number of the set and n the last number):


Leave a Reply