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}}.
Previously, I wrote about how you can generate the power set using a recursive algorithm. This time I'll show you how to use iteration.
Recall, that when we are generating a set for the power set, each element can either be in the set or out of the set. In other words, each set can be represented in binary form, where 1 means that the element is in the set and 0 means that it is not. For example, given a set {a, b, c}, the binary string 101 would represent {a, c}.
Generating the power set just comes down to generating all numbers from 0 to 2^n (since there are 2^n possible subsets) and converting the binary representation of the number into the set!
Here is the algorithm:
public static <E> List<List<E>> powerSet(final List<E> list) {
final List<List<E>> result = new ArrayList<>();
final int numSubSets = 1 << list.size(); // 2^n
for (int i = 0; i < numSubSets; i++) {
final List<E> subSet = new ArrayList<>();
int index = 0;
for (int j = i; j > 0; j >>= 1) { // keep shifting right
if ((j & 1) == 1) { // check last bit
subSet.add(list.get(index));
}
index++;
}
result.add(subSet);
}
return result;
}
