Problem: Given a set of numbers, find the powerset of that set.
Powerset of a set is defined as the set of all the subsets. Example: If the given set is [a,b,c], then powerset is
[ [1], [2], [3], [1,2], [2,3], [1,3], [1,2,3], [] ]

Solution: Since every possible subset has to be included in the powerset, this implies that the number of
sets in the powerset would be 2^{n} where n is the number of elements in the original set.
This 2^{n} comes into play because every element in the set can be included or omitted, giving us 2 possibilities
for each element in the set.
So, total number of possibilities = 2x2x2x... = 2^{n}

A recursive solution for this is as follows:

List <List<Integer>> powerSets; // kept global to avoid passing as an argument
void findPowerSet (List<Integer> originalSet, int pos, List<Integer> currSet)
{
if (originalSet == null)
return null;
if (pos >= originalSet.size() )
{
powerSets.add(currSet);
return;
}
List<Integer> currSet2 = currSet.clone();
currSet.push (originalSet.get(pos));
findPowerSet (originalSet, pos+1, currSet);
findPowerSet (originalSet, pos+1, currSet2);
}

Example execution:

An example running the above algorithm on [1,2,3] is as follows:
pos=0 [ 1 ]^{cs1} [ ]^{cs2}
/ \ / \
/ \ / \
/ \ / \
/ \ / \
pos=1 [1,2]^{cs1} [ 1 ]^{cs2} [ 2 ]^{cs1} [ ]^{cs2}
/ \ / \ / \ / \
/ \ / \ / \ / \
pos=2 [1,2,3]^{cs1} [1,2]^{cs2} [1,3]^{cs1} [1]^{cs2} [2,3]^{cs1} [2]^{cs2} [3]^{cs1} [ ]^{cs2}
pos=3 (currSet is added to the global powerSet at this stage)

Order analysis:
Stack depth goes to 'n' in every recursion leg.
The number of recursion legs is 2^{n}.
This means that in each leg of recursion, the call-stack is pushed and popped n times.
So total push-pop operations is n*2^{n}.

Non-recursive solution: The number of subsets in the powerset is 2^{n}. If we run a loop from
0 to 2^{n} and create a subset having numbers corresponding to 1s in the binary representation of loop variable,
then we will create 2^{n} subsets covering the entire range of the powerset.
This can be implemented as:

List <List<Integer>> findPowerSet (List <Integer> originalSet)
{
int count = originalSet.size();
long subsetCount = 2 << count;
List <List<Integer>> powerSet = new ArrayList <List <Integer>>();
for (long i=0; i < susbsetCount; i++)
{
List <Integer> subset = new ArrayList <Integer> ();
powerSet.add(subset);
// Add numbers to subset corresponding to 1s in the binary representation of i
long j=i;
int pos=0;
while (j > 0)
{
if (j&1 != 0)
subset.add (originalSet.get(pos));
j = j>>1;
pos++;
}
}
return powerSet;
}

Runtime of the above solution is also exponential but it atleast saves the stack space.
Note: The above function will work only for sets with size less than sizeof(long)=64.

Example execution:

For a set [1,2,3], the execution will be:
subsetCount=8
i=0, subset=[]
i=1, subset=[1]
i=2, subset=[2]
i=3, subset=[1,2]
i=4, subset=[3]
i=5, subset=[1,3]
i=6, subset=[2,3]
i=7, subset=[1,2,3]
powerSet = combination of all the above sets.

Further optimization: Consider the powerset for [a,b]
It would be P_{a,b} = [ [a], [b], [a,b], [] ]
If we add one more variable to the original set and make it [a,b,c], then the powerset becomes:
P_{a,b,c} = P_{a,b} + set formed by adding c to each set in P_{a,b}

This is a recursive relation like F_{1}(n) = F_{2}(F_{1}(n-1)) i.e a function which can be
expressed as some transform of a lower-order function

ArrayList <ArrayList<Integer>> findPowerSet (ArrayList <Integer> originalSet, int pos)
{
if (originalSet == null)
return null;
if (pos == originalSet.size())
{
ArrayList<ArrayList<Integer>> powerSet = new ArrayList <ArrayList<Integer>>();
ArrayList<Integer> subset = new ArrayList<Integer>();
powerSet.add(subset);
return powerSet; // return powerset with 1 element as [ [] ]
}
ArrayList<ArrayList<Integer>> subPowerSet = findPowerSet(originalSet, pos+1);
int currentVal = originalSet.get(pos);
// copy each subset into a new one, and add current element to it
ArrayList<ArrayList<Integer>> subPowerSet2 = new ArrayList<ArrayList<Integer>> ();
for (ArrayList <Integer> subset : subPowerSet)
{
ArrayList <Integer> subset2 = subset.clone();
subset2.add(currentVal);
subPowerSet2.add(subset2);
}
// merge the two sub-powersets into one
subPowerSet.addAll(subPowerSet2);
return subPowerSet;
}

Call-stack depth of this function is O(n) and number of recursion legs is 1.
Due to this, improvement over first function is clear enough.
Improvement over second function is that it does not do any bitwise operations to get the elements in each step.
And because of that the limit of 64 elements (sizeof(long)) in the original-set is removed.

Got a thought to share or found a bug in the code? We'd love to hear from you: