CC150 9.4

9_4.cpp

/* CC150 9.4 */

#include <iostream>
#include <vector>

using namespace std;

// Iteration approach
vector<vector<int>> subset(vector<int> set)
{
	vector<vector<int>> subsets;
	vector<int> emptySubset; // create an empty subset
	subsets.push_back(emptySubset);
	for (auto data : set) { // build subsets by adding an element each time
		int n = subsets.size();
		for (int i = 0; i != n; ++i) {
			vector<int> newSubset = subsets[i];
			newSubset.push_back(data);
			subsets.push_back(newSubset);
		}
	}
	return subsets;
}

// Combinatoric approach, direct print to screen
void subsetComb(vector<int> set)
{
	int n = set.size();
	for (int bin = 0; bin != (1 << n); ++bin) { // iterate through 0 to 2^n-1
		for (int bit = 0; bit != n; ++bit) { // translate binary representation into a set
			if (bin & (1 << bit))
				cout << set[bit] << " ";
		}
		cout << endl;
	}
}

int main()
{
	vector<int> set;
	int data;
	while (cin >> data)
		set.push_back(data);
	vector<vector<int>> subsets = subset(set);
	for (auto s : subsets) {
		for (auto i : s)
			cout << i << " ";
		cout << endl;
	}
	cout << endl << "Combinatorics approach:" << endl;
	subsetComb(set);
	return 0;
}

output

1 2 3
^Z

1
2
1 2
3
1 3
2 3
1 2 3