# Powerset Algorithm in C++

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:

``````{1,2,3}
{1,2}
{1,3}
{2,3}
{1}
{2}
{3}``````

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):

``````#include <iostream>

void printSet(int array[],int size){
int i;

for (i=1;i<=size;i++)
std::cout << array[i] << " ";
std::cout << std::endl;

return;
}

void printPowerset (int n){
int stack,k;

stack=0; /* 0 is not considered as part of the set */
k = 0;

while(1){
if (stack[k]<n){
stack[k+1] = stack[k] + 1;
k++;
}

else{
stack[k-1]++;
k--;
}

if (k==0)
break;

printSet(stack,k);
}

return;
}

int main(){

printPowerset(4);

return 0;
}``````

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

1
1 2
1 2 3
1 2 3 4
1 2 4
1 3
1 3 4
1 4
2
2 3
2 3 4
2 4
3
3 4
4

You can also implement the same idea 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):

``````void powersetRec(int s[], int k; int m, int n) {
if (m <= n) {
s[k+1] = m ;
printSet(s, k+1) ;
powersetRec(s, k+1, m+1, n) ; /* with m */
powersetRec(s, k, m+1, n) ; /*  without m */
}
}``````

If you want to perform something with the set elements other than print them you’ll just need to modify the printSet() function.

## 2 thoughts on “Powerset Algorithm in C++”

1. Lutu Putu

In printPowerset( ); I can input just the number of elements starting form 1(one) to that element.
But I need the inputs from user. That is, the user gives the number of elements, as well as the elements also. The elements can be anything- integers or even string.
How can I modify by this?
Thanks in advance.

2. Jack

If you can explain the algorithm first then it’s good. Directly looking at code scarying me.