powerset.cpp

/* TODO: write a recursive function to compute the powerset of a given set.
 * We will (ab)use vectors to represent our sets.  Recall that the powerset
 * of a set S is the set of all subsets.  E.g., if input was S = {1,2,3},
 * then the ouput would be P = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.
 * NOTE: return type should be vector<vector<int>>.  See below.
 * */
//Base case: The powerset of an empty set is just {} — no elements, only the empty set.

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

/* NOTE: V is given by value in case you want to modify it (to make a
 * smaller input for recursive calls). */
vector<vector<int>> powerset(vector<int> V)
{
	if (V.empty()) {
		return {{}};
	}
	int last=V.back(); // Get the last element of the set
	V.pop_back(); // Remove the last element to reduce the set size
	vector<vector<int>> subsets=powerset(V);     // Recursive call for the smaller set (without the last element)
	vector<vector<int>> result=subsets; // Copy the current subsets to create new subsets that include the last element
	for (auto& subset : subsets) {
		subset.push_back(last); //Add the last element to each subset
		result.push_back(subset);// Add this new subset to the result
	}
	return result; /* just so it compiles. */
}


int main()
{
	/* test code for power set function: */
	vector<int> S;
	int x;
	while (cin >> x) S.push_back(x);
	vector<vector<int>> P = powerset(S);

	cout << "{\n";
	for (size_t i = 0; i < P.size(); i++) {

		/* print the set P[i]... */

		for (size_t j = 0; j < P[i].size(); j++) {
			cout << P[i][j] << " ";
		}
		cout << "}\n";
	}
	cout << "}\n";
	return 0;
}

// vim:foldlevel=2
/*Recursive step: For each element in the set, we have two choices:
*Include it in the subset.
*Exclude it from the subset.
*So, given a set S = {1, 2, 3}, we can generate the powerset by:
*First considering the powerset of {1, 2} (without 3).
*Then, for each subset of {1, 2}, adding 3 to i*/