The bitmask DP intuition I wish I had at 14.

When I first saw bitmask DP, I memorized the pattern: dp[mask][last], iterate over submasks, done. I passed a few problems with it. Then I hit one that was slightly different and had no idea what to do, because I'd learned a recipe without understanding what any of the ingredients were for.

Here's the thing I wish someone had told me then: the bitmask is not the point. The bitmask is just a compact way to encode one specific kind of state. The real skill is state design — figuring out what information you actually need to carry forward. Once you have that, the bitmask is a footnote.

What does "state" mean?

In any DP, your state has to answer one question: given everything I've committed to so far, what do I still need to decide, and what does it cost from here?

The word "committed" is doing a lot of work. You're not caching a result — you're summarizing a partial construction well enough that you can continue it optimally without looking back at the history.

Bitmask DP appears when the set of things you've committed to matters, but the order usually doesn't — or when you need to track exactly which elements you've used. With N ≤ 20 or so, you can represent "I've used elements {0, 2, 5}" as the integer 0b100101. That's it. The rest is just DP on subsets.

Problem (a): Hamiltonian path

Classic. You have N ≤ 20 vertices, a directed graph, and you want to know if there's a path visiting every vertex exactly once. (CSES "Hamiltonian Flights" is one version; the AtCoder DP problem set has a matching-flavored cousin.)

The wrong way to think about it: "I need to remember which vertices I've visited." That's true, but it's not a state design — it's a wish list.

The right question: after visiting some subset S of vertices, ending at vertex v, can I extend this to a Hamiltonian path? My state is (mask, v) — mask is the set of visited vertices, v is where I am now. I commit to both simultaneously.

// dp[mask][v] = true if we can visit exactly the vertices in mask,
//               ending at vertex v
bool dp[1 << N][N];

dp[1 << start][start] = true;

for (int mask = 0; mask < (1 << N); mask++) {
    for (int v = 0; v < N; v++) {
        if (!dp[mask][v]) continue;
        for (int u = 0; u < N; u++) {
            if (mask & (1 << u)) continue; // already visited
            if (has_edge[v][u]) {
                dp[mask | (1 << u)][u] = true;
            }
        }
    }
}

The transition is: if I'm at v having visited mask, I can move to any unvisited neighbor u, producing state (mask | (1 << u), u). Notice the transition falls out of the state definition — I didn't think about transitions first. I thought about state, and the transition became obvious.

Problem (b): Assignment / matching

N jobs, N workers, cost matrix. Assign each job to exactly one worker, minimize total cost. This is AtCoder DP "O - Matching" territory, or the classic assignment problem when N is small.

Here the state looks slightly different. I process jobs one by one. After handling jobs 0..k-1, my state is: which workers have I already assigned? That's the mask. The job index is implicit — it's just popcount(mask), the number of bits set, because I assign jobs in order.

// dp[mask] = minimum cost to assign the first popcount(mask) jobs
//            using exactly the workers in mask
long long dp[1 << N];

dp[0] = 0;

for (int mask = 0; mask < (1 << N); mask++) {
    int job = __builtin_popcount(mask); // which job are we assigning?
    if (job == N) continue;
    for (int w = 0; w < N; w++) {
        if (mask & (1 << w)) continue; // worker already used
        dp[mask | (1 << w)] = min(dp[mask | (1 << w)],
                                   dp[mask] + cost[job][w]);
    }
}

Same shape, different interpretation. The mask means "workers committed to". The job index is recovered for free from the mask. This is worth pausing on — a lot of bitmask DP states carry implicit information you don't need to store separately.

Problem (c): TSP closed tour

Now add the requirement that after visiting all N vertices you return to the start, minimizing total edge weight. This is the Travelling Salesman on small N.

The state is still (mask, v) — same as Hamiltonian path. What changes is the answer extraction: after filling the full mask, I check the cost of returning home. The underlying DP is identical. The only thing I needed to adjust was what I asked at the end.

When you can name what your state means in one sentence — "the set of committed choices, and the current position" — the bitmask is the smallest detail. Everything else follows from that sentence.

Students who memorize dp[mask][last] without understanding what mask and last represent will get stuck the moment a problem doesn't fit the template exactly. Mira, one of my students, spent two hours on a subset-sum variant before we talked through what "committed" meant in that context — once she rephrased the state as "the subset of items I've already placed", the solution was ten lines.

The actual mental checklist

When I see a problem and suspect bitmask DP, I ask these in order:

1. What am I building up? (a permutation, an assignment, a subset, a tour)
2. What partial information do I need to carry to make optimal decisions going forward? That's my state.
3. Can that information be encoded as a subset of some small set (N ≤ 20)? Then the mask is just how I represent it.
4. What does one transition look like? (Add one more element, make one more assignment.)
5. What's the base case — the empty commitment?

The bitmask isn't a technique. It's a data structure choice for representing a specific kind of state. Get the state right and you've done the hard part. The integer arithmetic — mask | (1 << i), mask & (1 << i), iterating submasks — is mechanical and learnable in an afternoon.

If you're preparing for OI and you've seen bitmask DP before but it doesn't feel solid yet, pick one problem — the assignment one is cleanest — and before writing any code, write down in words what your state represents. Force yourself to be precise. "dp[mask] is the minimum cost to assign the first popcount(mask) jobs using exactly the workers in mask." If you can write that sentence, you can write the code.