#include<stdio.h>
#include <set>
#include <map>
#include <iostream>
using namespace std;
void print_set( set<int> S ) {
	set<int>::iterator i;
	
	if ( S.size() == 0) {
		printf( "NIL\n" );
		return;
	}
	for (i=S.begin(); i != S.end(); i++)
		printf( "%d ", *i );
	printf( "\n" );
}




// Power set (P(S)), done with recursion
//
// From wikipedia: the power set of the empty set is the set containing the empty set 
// and the power set of any other set is all the subsets of the set containing some 
// specific element and all the subsets of the set not containing that specific element.

void power_set_rec( set<int> &S, set<set<int> > &res ) {

	if (S.size() == 0) {
		set<int> a;
		res.insert(  a );
		return;
	}	

	set<int>::iterator i;
	set< set<int> >::iterator j;

	for (i=S.begin(); i != S.end(); i++) {
		// I'm not quite sure if there is a better
		// way to do this. Right now in order to get T
		// I copy S to another set and remove i from there
		set<int> T=S;

		T.erase( *i );


		// Same goes for restmp, lots of (maybe) unnecessary  copying
		set<set<int> > restmp;

		
		power_set_rec( T, restmp );

		
		for (j=restmp.begin(); j != restmp.end(); j++) {
			// Basically we insert each j from restmp into
			// res two times: once as it is and another
			// time with *i added. 
			res.insert( *j );
			

			// Another instance of unnecessary copying
			set<int> tmp = *j;
								
			tmp.insert( *i );
			res.insert( tmp  );
		}
	}
}



// Memo map, for use with the memoization version
map< set<int> , set< set<int> > > MEMO;

// Memoized version of the above. Much faster
void power_set_memo( set<int> &S, set<set<int> > &res ) {

	if (S.size() == 0) {
		set<int> a;
		res.insert(  a );
		return;
	}	

	set<int>::iterator i;
	set< set<int> >::iterator j;

	for (i=S.begin(); i != S.end(); i++) {
		// I'm not quite sure if there is a better
		// way to do this. Right now in order to get T
		// I copy S to another set and remove i from there
		set<int> T=S;

		T.erase( *i );


		// Same goes for restmp, lots of (maybe) unnecessary  copying
		set<set<int> > restmp;

		if (MEMO.find( T ) != MEMO.end() ) {
			// Found it!
			restmp = MEMO[T];
		} else {

			power_set_memo( T, restmp );
		}
		MEMO[ T ] = restmp;
		
		for (j=restmp.begin(); j != restmp.end(); j++) {
			// Basically we insert each j from restmp into
			// res two times: once as it is and another
			// time with *i added. 
			res.insert( *j );
			

			// Another instance of unnecessary copying
			set<int> tmp = *j;
								
			tmp.insert( *i );
			res.insert( tmp  );
		}
	}
}






int main( void ) {
	
	set<int> S;
	S.insert( 1 );
	S.insert( 2 );
	S.insert( 3 );
	S.insert( 4 );
	S.insert( 5 );
	S.insert( 6 );
	S.insert( 7 );
	S.insert( 8 );
	S.insert( 9 );

	printf( "Input set: " );
	print_set( S );


	set<set<int> > res;
	set<set<int> >::iterator it;
	
	printf( "Calculating w/ rec. function...\n" );
	power_set_rec( S, res );
	for (it = res.begin(); it != res.end(); it++)
		print_set( *it );


	res.erase( res.begin(), res.end() );

	printf( "\n\nCalculating w/ rec. function and memoization...\n" );
	power_set_memo( S, res );

	for (it = res.begin(); it != res.end(); it++)
		print_set( *it );

	printf( "MEMO table size: %d entries\n", MEMO.size() );

}