Power Set

Write a method to return all subsets of a set.

Solution

Let’s consider the base case, a set with one member : {1}. The power set in this case is a set with two members, the empty set and the set with one element : {}, {1}. The base case can be generated by combining the empty set’s power set, and the empty set’s power set plus an additional element.

Now let’s expand upon the base case. Consider a set with two elements, {1, 2}. To generate the power set we can take the power set for {1} and add 2 to each subset.

{}, {1}
{}, {1}, {2}, {1,2}

We have a base case, and we have the recursion. Let’s build our function.

def power_set(array):
  if(len(array) == 0):
    return [[]]

  subsets = power_set(array[:-1])
  new_subsets = []

  for subset in subsets:
    new_subsets.append( subset + [array[-1]] )

  return subsets + new_subsets