Bitmask DP

At a glance

The instinct

Brute force over orders is n!; brute force over subsets is 2^n. When the problem only cares about which items have been handled (plus maybe one extra fact such as "where am I now"), not the exact order, collapse all orders that used the same set into one state. An int with n bits is a perfect, hashable, array-indexable set. With n ≤ 20, 2^20 ≈ 10^6 states fit easily.

Recognise it

Not this pattern if...

• n is 40+ (consider meet-in-the-middle) or 10^3+ (it is knapsack, greedy or graph search).
• Items are interchangeable and only the count or sum matters - plain knapsack is enough.
• You only need to list subsets, not optimise over them - that is backtracking.

Memory hack

Analogy: a festival wristband with a row of stamps. The bouncer at each stage only cares which stamps you already have and which stage you are standing at - not the order in which you collected them.

DP framing:

• State - dp[mask] or dp[mask][last]: best cost having used exactly the items in mask.
• Choice - the next unused item to add, or a whole submask to form the next group.
• Base case - dp[0] = 0, or dp[1 << start][start] = 0 for path problems.
• Order - increasing mask works, because adding bits only makes the integer bigger (BFS if every move costs 1).

Say it out loud in the interview:

1. "n is at most 20, so I can afford 2^n states; bit i means item i is used."
2. "The extra dimension I need is ... (last node / current group load / nothing)."
3. "Transitions add one bit or a submask; answer is at the full mask (1 << n) - 1."

How it works

Trace for Minimum Number of Work Sessions: tasks [1, 2, 3], session length 3. dp[mask] = fewest sessions to finish the tasks in mask; a submask may form one session if its sum ≤ 3.

Every row only looks at smaller masks, so a simple increasing loop is a valid order. For unit-cost moves on a graph (visit all nodes) the same (node, mask) states are explored with BFS instead.

Java template

import java.util.*;

class BitmaskDp {
    static final int INF = Integer.MAX_VALUE / 2;

    // 1) Path / TSP shape: dp[mask][last] = min cost to visit `mask`, ending at `last`.
    static int shortestCoverPath(int[][] cost) {
        int n = cost.length, full = (1 << n) - 1;
        int[][] dp = new int[1 << n][n];
        for (int[] row : dp) Arrays.fill(row, INF);
        for (int s = 0; s < n; s++) dp[1 << s][s] = 0;          // base: start anywhere
        for (int mask = 1; mask <= full; mask++) {
            for (int last = 0; last < n; last++) {
                if ((mask & (1 << last)) == 0 || dp[mask][last] == INF) continue;
                for (int nxt = 0; nxt < n; nxt++) {
                    if ((mask & (1 << nxt)) != 0) continue;      // already used
                    int nm = mask | (1 << nxt);
                    dp[nm][nxt] = Math.min(dp[nm][nxt], dp[mask][last] + cost[last][nxt]);
                }
            }
        }
        int best = INF;
        for (int last = 0; last < n; last++) best = Math.min(best, dp[full][last]);
        return best;
    }

    // 2) Partition shape: split all items into the fewest groups whose sum <= cap.
    static int minGroups(int[] items, int cap) {
        int n = items.length, full = (1 << n) - 1;
        int[] sum = new int[1 << n];
        for (int mask = 1; mask <= full; mask++) {
            int low = Integer.numberOfTrailingZeros(mask);
            sum[mask] = sum[mask & (mask - 1)] + items[low];      // reuse smaller subset
        }
        int[] dp = new int[1 << n];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int mask = 1; mask <= full; mask++) {
            for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {  // all non-empty submasks
                if (sum[sub] <= cap && dp[mask ^ sub] != INF) {       // problem-specific "group is valid"
                    dp[mask] = Math.min(dp[mask], dp[mask ^ sub] + 1);
                }
            }
        }
        return dp[full];
    }
}

Complexity

3^20 is about 3.5 · 10^9, so submask loops are realistic only up to about n = 15-16; above that, prefer one-item-at-a-time transitions.

Variations

• Hamiltonian path / TSP - dp[mask][last]. Find the Shortest Superstring, classic travelling salesman.
• BFS with a visited mask - unit edges, multiple starts at once. Shortest Path Visiting All Nodes.
• Assignment / matching - the next person is popcount(mask), so the mask alone is the state. Minimum XOR Sum of Two Arrays.
• Partition into groups - submask enumeration, or dp[mask] = (groups, load of the open group) to stay at O(2^n · n). Minimum Number of Work Sessions to Finish the Tasks.
• k buckets, minimise the max - dp[child][mask] with submask choice, or backtracking with pruning. Fair Distribution of Cookies.
• Game states - memoise win/lose on the set of numbers already taken. Can I Win.
• Profile DP - the mask is the shape of a grid column boundary (domino tilings); a harder relative.

Common mistakes

• Java precedence: mask & 1 << i == 0 does not compile (and in C it is wrong); always write (mask & (1 << i)) == 0.
• Writing sub = (sub - 1) & mask with a loop condition that allows sub == 0 - it wraps back to mask forever.
• Forgetting the extra dimension (e.g. current node) and merging states that are genuinely different.
• Memory blow-up: int[1 << 20][20] is about 80 MB - check whether last can be dropped or use BFS with a visited array.
• Using 1 << n with n >= 31 in an int; switch to long masks or reconsider the approach.

All practice problems

3 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.