Bitmask DP Without the Panic: A Small-State Survival Guide

The Panic Is Optional

Bitmask DP has a reputation for looking like a spell. You see 1 << n, nested loops, and suddenly the problem feels like it belongs to someone who has a whiteboard instead of a pulse.

The trick is to stop thinking about the mask as a clever hack. A mask is just a compact set. If the problem asks you to choose, visit, assign, partition, or remember a small collection of things, a bitmask might be the cleanest way to store that state.

When To Reach For It

• Small n: usually 20 or less for 2^n states, lower if each transition is expensive.
• Set memory: the answer depends on which items have already been used.
• Order plus set: paths like traveling-salesman-style problems need both the last item and the visited set.
• Partitioning: groups, subsets, or compatibility checks can often be precomputed per mask.

The Basic Shape

Most small-state DP starts with one question: what does dp[mask] mean?

const total = 1 << n;
const dp = Array(total).fill(Infinity);
dp[0] = 0;

for (let mask = 0; mask < total; mask++) {
  for (let i = 0; i < n; i++) {
    if ((mask & (1 << i)) !== 0) continue;

    const next = mask | (1 << i);
    dp[next] = Math.min(dp[next], dp[mask] + cost(mask, i));
  }
}

Read that as a sentence: "from the set I already have, try adding one missing item." That is the whole machine.

Common Variants

State	Meaning
dp[mask]	Best answer after selecting exactly the items in mask.
dp[mask][last]	Best answer for mask when the current path ends at last.
valid[mask]	Whether a subset can form a group, segment, or partition.
submask loop	Try every subset inside a set for grouping transitions.

The Submask Loop

This is the line that looks the strangest the first time you see it:

for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
  // sub is one non-empty subset of mask
}

It walks every subset of mask without touching numbers that are not contained in the original set. Once that clicks, a lot of partition DP problems stop being mystical and start being bookkeeping.

Takeaway

Bitmask DP is not about being fancy. It is about admitting the state is a set, then storing that set in the smallest practical form. Define the state in plain English first. The code gets much less scary after that.