# 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:

Table 1: The representation of the decimal number, binary number and corresponding set.
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.
// The number of set bits in the mask is the number of elements we
// pick for this specific set
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;
}

Published on by .