Bit masks for subsets

For a universe of n ≤ 31 items (63 with long), the subset with items i1, i2, … is the number (1 << i1) | (1 << i2) | …. Every subset gets a unique number between 0 and 2^n - 1, and the empty set is 0.

Set operations map directly onto bit operators.

The numbers 0 to 2^n - 1 are exactly all subsets of n items. Loop mask over that range and, for each, add item i when bit i is set. The animation lists every subset in order and highlights the chosen items.

The total cost is O(2^n · n). That is fine up to about n = 20-25 (a million to 33 million subsets), and impossible beyond that: the count doubles with every additional item.

1static List<List<Integer>> allSubsets(int[] items) {
2    int n = items.length;
3    List<List<Integer>> result = new ArrayList<>();
4    for (int mask = 0; mask < (1 << n); mask++) {
5        List<Integer> subset = new ArrayList<>();
6        for (int i = 0; i < n; i++) {
7            if ((mask & (1 << i)) != 0) subset.add(items[i]);
8        }
9        result.add(subset);
10    }
11    return result;
12}

1int n = items.length;
2for (int mask = 0; mask < (1 << n); mask++) {
3    List<Integer> subset = new ArrayList<>();
4    for (int i = 0; i < n; i++) {
5        if ((mask & (1 << i)) != 0) {      // is bit i set?
6            subset.add(items[i]);
7        }
8    }
9    print(subset);
10}

To enumerate every subset of a given mask m, start at sub = m and repeatedly step to the next smaller submask with sub = (sub - 1) & m. Subtracting 1 may switch on bits outside m; ANDing with m removes them and lands on the next submask in decreasing order. Stop when sub reaches 0 and handle the empty submask separately.

A mask with k set bits has 2^k submasks, and enumerating all submasks of all masks of n bits costs 3^n in total (each item is in the mask and in the submask, in the mask but not the submask, or in neither).

1for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
2    process(sub);
3}
4process(0);                       // the empty submask

1for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
2    process(sub);                  // next submask, in decreasing order
3}
4process(0);                        // the empty submask

To visit only the 1 bits of a mask, repeatedly take the lowest set bit and remove it: for (m = mask; m != 0; m &= m - 1), with Integer.numberOfTrailingZeros(m) giving its index. This runs once per set bit, so sparse masks are cheap.

This is the standard way to loop over the members of a subset, or over the neighbours of a vertex stored as a bitmask in a graph algorithm.

1for (int m = mask; m != 0; m &= m - 1) {
2    int lowest = m & -m;                             // isolate the lowest set bit
3    int index = Integer.numberOfTrailingZeros(m);    // its position
4    visit(index);
5}

A mask can describe the state of a process: which items are already used, which switches are on, which cells are filled. A move that adds item i is mask | (1 << i), a move that toggles switch i is mask ^ (1 << i), and the goal state is a specific mask such as (1 << n) - 1.

Because there are at most 2^n states, a breadth-first search over masks, or a table indexed by mask, solves puzzles like lights-out and the shortest way to visit all items.

1// fewest moves to turn all n lights on, when each button toggles a set of lights
2static int fewestPresses(int n, int[] buttonMask) {
3    int full = (1 << n) - 1;
4    int[] dist = new int[1 << n];
5    Arrays.fill(dist, -1);
6    dist[0] = 0;
7    Deque<Integer> queue = new ArrayDeque<>(List.of(0));
8    while (!queue.isEmpty()) {
9        int state = queue.poll();
10        if (state == full) return dist[state];
11        for (int b : buttonMask) {
12            int next = state ^ b;                      // press the button
13            if (dist[next] < 0) { dist[next] = dist[state] + 1; queue.add(next); }
14        }
15    }
16    return -1;
17}

Bitmask DP stores one value per subset: dp[mask] is the best answer for exactly the items in mask. You compute it from smaller masks by adding one item at a time. The table has 2^n entries and each transition tries n items, giving O(n · 2^n), far better than the n! of trying every order.

Classic examples are assigning n tasks to n people at minimum cost and the travelling salesman problem (O(n² · 2^n)). Dynamic programming itself is covered in Chapter 23; here is the shape.

1// minimum total cost to give each person i exactly one task, n <= 20
2static int assign(int[][] cost) {
3    int n = cost.length;
4    int[] dp = new int[1 << n];
5    Arrays.fill(dp, Integer.MAX_VALUE);
6    dp[0] = 0;
7    for (int mask = 0; mask < (1 << n); mask++) {
8        if (dp[mask] == Integer.MAX_VALUE) continue;
9        int person = Integer.bitCount(mask);          // tasks used so far = next person
10        if (person == n) continue;
11        for (int task = 0; task < n; task++) {
12            if ((mask & (1 << task)) != 0) continue;
13            int next = mask | (1 << task);
14            dp[next] = Math.min(dp[next], dp[mask] + cost[person][task]);
15        }
16    }
17    return dp[(1 << n) - 1];
18}