# Efficient Powerset Generation in Java

One common interview question is to generate the power set of a set. The power set of a set $S$, written $\mathcal{P}(S)$ is the set of all subsets of $S$. So, $\mathcal{P}([3, 1, 4])$ is:

[ [], [3], [1], [3, 1], [4], [3, 4], [1, 4], [3, 1, 4] ]

One clever way to generate the power set is to use integers as a bit mask for
the elements to select. So, if you had `0101`

you would select the 0th and 2nd
item from the original set. For the example above, it looks like:

i | binary number | set |
---|---|---|

0 | 000 | `[]` |

1 | 001 | `[3]` |

2 | 010 | `[1]` |

3 | 011 | `[3, 1]` |

4 | 100 | `[4]` |

5 | 101 | `[3, 4]` |

6 | 110 | `[1, 4]` |

7 | 111 | `[3, 1, 4]` |

Extending this approach into Java looks something like the code below.

public static int[][] powerset(int[] src) { // Java's max array size is Integer.MAX_VALUE, which is 2^31 - 1. So, // the max size we can handle is 30 elements, since the powerset will be // 2^30 elements long. assert src.length < 31 : "length must be less than 31"; int powersetSize = 1 << src.length; // Initialize array of nulls that we'll fill below. int[][] powerset = new int[powersetSize][]; for (int i = 0; i < powersetSize; i++) { // We can use integers as masks for what to select, e.g. 0010 means // select the first element. int mask = i; // The number of set bits in the mask is the number of elements we // pick for this specific set int destSize = Integer.bitCount(mask); int[] dest = new int[destSize]; int destIndex = 0; // Loop through the set bits by clearing the least significant bit // until no bits are set. for (int m = mask; m != 0; m = m & (m - 1)) { int lowestBit = Integer.lowestOneBit(m); // Translate the lowestBit into an index into the src array. We // want the position of the low bit in the integer which we get // with log2(n). log2(n) is efficiently computed by counting // the leading number of zeroes. int srcIndex = 31 - Integer.numberOfLeadingZeros(lowestBit); dest[destIndex] = src[srcIndex]; destIndex++; } powerset[i] = dest; } return powerset; }