^{N}elements. This is evident from the above example.

Here is how our method works.

All the subsets can be identified by an integer. The binary representation of that integer says which elements from the original set present in that subset.

For example let us consider a set of two elements {1,2}, the power set of this can be represented by four integers

0 = 0000 – Empty subset

1 = 000**1** – Fist element is present

2 = 00**1**0 – Second element is present

3 = 00**11** – First and Second elements are present

In the following C++ program, the outer loop runs from 0 to 2^{n} where **n** is the size of the set. For each integer, the inner loop checks for set bit positions and accordingly add those numbers to the current subset.

Since we have to generate all the possible subsets, the complexity of this method is O(2^n).

#include <iostream>

#include <set>

#include <vector>

using namespace std;

//Generates the power set of integers provided in inputSet,

//output in pSet

void generatePowerSet( vector<int> &inputSet, set< set<int> > &pSet )

{

int i = 0;

int n = inputSet.size();

//There will be 2^n subsets; generate them

while ( i < (2 << n) )

{

set<int> subSet;

int j = 0;

int k = i;

while( k&(k-1) ) //Until k contains at-least one set bit

{

//If jth bit is set, add the jth element to the subset

if( k & 1)

{

subSet.insert( inputSet[j] );

}

k = k >> 1;

j++;

}

//Add the subset to the powerset

pSet.insert(subSet);

i++;

}

}

//Utility to print the powerset

void printPowerSet( set< set<int> > &pSet)

{

set< set<int> >::iterator setIter;

set<int>::iterator intIter;

for( setIter = pSet.begin(); setIter != pSet.end(); ++setIter )

{

cout<<"{ ";

for( intIter = setIter->begin(); intIter != setIter->end(); intIter++ )

{

cout<<*intIter<<" ";

}

cout<<"}"<<endl;

}

}

int main()

{

int n; // number of elements

cin>>n;

vector<int> intSet;

int i;

//Read the set elements

for( i = 0; i < n; i++ )

{

int x;

cin>>x;

intSet.push_back(x);

}

set< set<int> > powerSet;

generatePowerSet( intSet, powerSet );

printPowerSet( powerSet );

return 0;

}