Computing the powerset

Problem Statement:

Generate the power set of a set \(S\) of \(n\) elements.

This is also a nice, short, and quick interview question. Straight away we know that our algorithm will be exponential, \(O(2^n)\) since that’s the size of the powerset.

We can easily think about this recursively. The power set of the empty set is a set with one element, the empty set. The empty set is part of the powerset of any set. Then, think of an element \(x_i\) from \(S\). Assuming we have the solution for the powerset \(P_1\) of \(S - \{x_i\}\) }, we can put \(x_i\) into every element of that set, and take the union of it with \(P_1\):

Translating this into simple code is as follows. In the code, \(i\) is the index from which we want the to take the powerset of \(S\). We get the whole powerset of \(S\) when \(i=0\).

def powerset(s):
  return powerset1(s,0)

def powerset1(s,i):
  if(i == len(s)): return [[]]
  
  p1 = powerset1(s,i+1)
  
  ret = []
  for p in p1:
    ret.append([s[i]] + p)
  return ret + p1

Testing it with a simple example…

> print(powerset([1,2,3]))
[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

This confirms the code is correct.