Problem

Print the power set of a given set of numbers, in the lexicographically sorted order.

Solution

https://ideone.com/DXm5uR

Explanation

A power set of a set (set here is the mathematical collection of numbers) is the set of all its subsets. It can be done by recursive method or iterative method. Both are shown in the solution. Both the solution are exponential in time complexity, as the size of the output is exponential. But the recursive approach is better here, because, it uses maximum stack memory of O(n). While the iterative method is incrementaly creating the answer and storing it in the memory, pushing its space complexity to be same as the time complexity that is exponential O(n*2^(n-1))

Complexity

Size of a power set is 2^n if size of set is n. Not only this, each element of power set will have elements in it, ranging from 0-n. We have to print the whole power set i.e., all the subsets of given set. Hence the problem is inherently exponential. Total n*2^(n-1) numbers to be printed. Why?

Code

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void f(int i, vector<int> &v, vector<int> &ans){
	while(i<v.size()){
		for(int x: ans)	cout<<x<<'\t';
		cout<<v[i]<<endl;
		ans.push_back(v[i]);
		f(++i, v, ans);
		ans.pop_back();
	}
}
int main() {
	int n,x;
	vector<int> v;
	cin>>n;
	while(n--&&cin>>x)	v.push_back(x);
	sort(v.begin(),v.end());
	vector<int> rec_temp;
	f(0,v,rec_temp);	//	recursive approach
	return 0;
	// iterative approach
	vector<vector<int>> ans;
	vector<int> temp;
	n = v.size();
	for(int i=n-1; i>=0; i--){
		x = ans.size();
		for(int j=0; j<x; j++){
			temp = vector<int>(1,v[i]);	//	array containing single element v[i]
			temp.insert(temp.end(),ans[j].begin(),ans[j].end());
			ans.push_back(temp);
		}
		temp = vector<int>(1,v[i]);
		ans.push_back(temp);
	}
	ans.push_back(vector<int>(0));
	x = ans.size();
	for(int i=x-1; i>=0; i--){
		for(int j=0; j<ans[i].size(); j++)	cout<<ans[i][j]<<'\t';
		cout<<endl;
	}
	return 0;
}

Ideone it!