/* Warm - up Problem 0B: Random Subsets
There are 2^n possible subsets of a set of n elements
(Two possibilities for each of the n members : in or out).
That's growing exponentially, so it can take a very long time print 
them to a list.  What if instead of generating all possible subsets, 
we just generate a few random subsets?  That way, we can get a rough 
sense for what the subsets look like.

To generate a random subset from a set we visit every element of the set, 
one after the other, and flip a fair coin to decide whether or not to 
include that element in the resulting subset.

As long as the coin tosses are fair, this produces a uniformly - 
random subset of the given set.

Write a function

	set<int> randomSubsetOf(set<int>& s);

that accepts as input a set<int> and returns a random subset of that set.
Your algorithm should be recursive and not use any loops(for, while, etc.) */

#include <set>
using std::set;
#include <iostream>
using std::cin;
using std::cout;
#include <vector>
using std::vector;

vector< set<int> > subsetsOf(set<int>& s);

int main() {
	int ints[] = { 10,20 };
	set<int> values(ints, ints + 2);

	for (set<int> subset : subsetsOf(values)) {
		for (int i : subset) {
			cout << i << " ";
		}
		cout << '\n';
	}
	cin.get();
}

vector< set<int> > subsetsOf(set<int>& s) {
	
	if (s.empty()) { //base case
		vector< set<int> > result;
		result.push_back(s);
		return result;
	}
	else {
		set<int>::iterator itr = s.begin();
		int elem = *itr;
		s.erase(elem);
		set<int> rest = s;
		vector< set<int> > result;
		for (set<int> s : subsetsOf(rest)) {
			result.push_back(s);
			s.insert(elem);
			result.push_back(s);
		}
		return result;
	}
}