Sunday, September 18, 2016

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}}`.

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

Here is the algorithm:

```public static <E extends Comparable<E>> List<List<E>> subsets(final List<E> list) {
final List<List<E>> result = new ArrayList<>();

// if the list is empty there is only one subset, which is the empty set
if (list.isEmpty()) {
return result;
}

// otherwise, get the first element
final E first = list.get(0);

// find the subsets of the rest of the list
final List<E> rest = list.subList(1, list.size());
final List<List<E>> subsets = subsets(rest);

// create new subsets by inserting the first element into each subset
for (final List<E> subset : subsets) {
final List<E> newSubset = new ArrayList<>(subset);
}

return result;
}
```