C, C++ code for returning all the subsets of a set.

Logic:

Consider a set \[{5, 9, 1, 6, 8, 10}\]

Basic permutation and combination tell us that there will be $2^n$ subsets of a set with n elements. The subset of the original set can be done as follows: Evaluate the subsets of ${5, 9, 1, 6, 8}$ and create a copy ${5, 9, 1, 6, 8}$ and push in one of it $10$. This way the problem can be reduced to recursion. Similarly, the subsets of ${5, 9, 1, 6, 8}$ can be evaluated and returned to the calling function.

Algorithm:

vector<vector<int> > getSubsets(vector<int> set, int index){
	vector<vector<int> > allsubsets;
	if(index == set.size()/*reached the end of the sets thus now add an empty set to the list*/){
	allsubsets.push_back(vector<int>());
	}else{
	allsubsets = getSubsets(set, index+1);
	int item = set[index];
	vector<vector<int> > moresubsets;
	for (vector<int> subset: allsubsets) {
	vector<int> newsubset(subset);
	newsubset.push_back(item);
	moresubsets.push_back(newsubset);
	}
	for (vector<int> v: moresubsets ) {
	allsubsets.push_back(v)
	}
	}
	return allsubsets;
	}

What this code does?

We enter the function with a call on the original set and value of index =0. In each, we evaluate all the subsets when we do not consider element at location index. Now in all the sets already we have created, we create copy of each of these. In these new copy, we put in the new element. And return this new allsubsets thus created.