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:


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;


void printPowerset (int n){
    int stack[10],k;

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

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


        if (k==0)



int main(){


    return 0;

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

1 2
1 2 3
1 2 3 4
1 2 4
1 3
1 3 4
1 4
2 3
2 3 4
2 4
3 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.


Leave a Reply

Your email address will not be published. Required fields are marked *