Power Set Algorithm

The power set of a set S is the set of all subsets of S including the empty set and S itself. For example, the power set of {1, 2, 3} is {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. In an interview, I was asked to write an algorithm to find the power set of a given set.

The problem can be solved using recursion. We know that if the initial set has only one element {a} then its power set is {{}, {a}}.

Here is the algorithm:

public <E extends Comparable<E>> List<List<E>> powSet(List<E> list){

  List<List<E>> result = new ArrayList<List<E>>();
  if(list.isEmpty()){
    result.add(new ArrayList<E>());
    return result;
  }
  else if(list.size() == 1){
    List<E> empty = new ArrayList<E>() ;
    List<E> oneE = new ArrayList<E>(list) ;
    result.add(empty);
    result.add(oneE);
    return result;
  }
  else{
    E first = list.remove(0);
    List<List<E>> subsets = powSet(list);

    for(List<E> subset : subsets){
      result.add(subset);

      List<E> tmp = new ArrayList<E>(subset) ;
      tmp.add(first);
      Collections.sort(tmp);
      result.add(tmp);
    }
    return result;
  }
}

More Interview Posts