Given a set of numbers, how do we generate its power set?

For example for the set {1,2} the power set is given below.

{ {}, {1}, {2}, {1,2} }

A power set is nothing but all the possible subsets of a given set. If a set contains N elements, it's power set contains 2

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

2 = 00

3 = 00

In the following C++ program, the outer loop runs from 0 to 2

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

^{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 present2 = 00

**1**0 - Second element is present3 = 00

**11**- First and Second elements are presentIn 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; }