#CodeChallenge return all power sets from a given array, powersets include number cero.

PowerSetFromArray.cpp

#include <vector>
using namespace std;

// O(n * 2^n) time | O(n * 2^n) space
vector<vector<int>> helper(vector<int> array, int idx) {
	if (idx < 0) return {{}}; // Return empty array
	vector<vector<int>> subsets = helper(array, idx - 1);
	int length = subsets.size();
	int word = array[idx]; // starts from last element
	for (int j = 0; j < length; j++) {
		vector<int> currentSet = subsets[j];
		currentSet.push_back(word);
		subsets.push_back(currentSet);
	}
	return subsets;
}

vector<vector<int>> recursivePowerset(vector<int> array) {
  return helper(array, array.size() - 1);
}

// O(n * 2^n) time | O(n * 2^n) space
vector<vector<int>> iterativePowerset(vector<int> array) {
  vector<vector<int>> set{{}};
	for (int i = 0; i < array.size(); i++) {
		int number = array[i];
		int length = set.size(); // IMPORTANT!
		for (int j = 0; j < length; j++) {
			vector<int> currentSet = set[j];
			currentSet.push_back(number);
			set.push_back(currentSet);
		}
	}
  return set;
}