Bitmask DP: subsets as states and the cost of enumerating them

Why this matters when you build with AI

Ask an AI tool for a solution over subsets of 20 items and you will often get a loop over every subset with an inner loop over every submask. Written that way, the work is 3^20, about 3.5 billion steps. The code is short and reads well, and the sample has 3 items, so nothing looks wrong until the judge stops it.

The same tool will often pick the right state, a bitmask, but skip the count. A bitmask is a number whose bits say which items are in a set. That makes subsets cheap to store, but a table with 2^20 rows is only fast if each row does a small amount of work. This lesson shows how to count that work before you write the loop, and how to check the result against a brute force.

A prompt that asks for the count and the state meaning, so you can check both:

Write C++17 code for this problem. The first line has n, with n at most 20.
The next n lines each have n integers: cost[i][j] is the price for baker i to bake order j,
or -1 if baker i cannot do it. Each baker bakes exactly one order and each order is baked by one baker.
Print the smallest total cost, or -1 if no full assignment exists.
Before the code, state what a DP state means in one sentence, give its number of states,
the work per state, and the total. Then give the code and its output on this sample:
3 / 1 2 3 / 2 4 6 / 3 6 9. The output starts with 10.

A good answer defines the state as a set of finished orders, writes the total as 2^n times n, and prints 10. A bad answer uses the mask as a number without saying what it stands for, or claims a complexity that does not match the loops. Compare the code with the brute force in the worked example before you use it.

Terms used

A mask is an integer whose bit j says whether item j is in a set. Bit 0 is the lowest bit. Mask 0b1011 (decimal 11) is the set {0, 1, 3}.
The popcount of a mask is the number of bits set to 1. It is the size of the set. In C++ it is __builtin_popcount(mask).
A submask of mask is any mask s whose set bits are all also set in mask. The submasks of 0b101 are 0b000, 0b001, 0b100 and 0b101.
A profile is the part of the state that a grid DP needs to remember. In a broken profile DP the profile holds one bit per column, updated cell by cell.
Sum over subsets (SOS) is a way to compute, for every mask, the sum of values over its submasks in n passes.
Brute force here means trying every assignment or every subset. It is only used for small inputs.

The idea: a mask is a set you can index

Take n = 4 items numbered 0 to 3. The set {0, 2} is the mask 0b0101, which is 5 in decimal. The bit for item j is (mask >> j) & 1. Adding item j is mask | (1 << j), and removing it is mask & ~(1 << j). These three operations are cheap, so a mask works well as a state.

Every mask of n items is a state, so there are 2^n states. For n = 20 that is 1,048,576 states. A DP over masks is fast when the work per state is small, for example n steps. It is slow when the work per state is 2^n, as it is in some naive loops over submasks.

Every bitmask DP has three parts. The state is a mask with a stated meaning. The transition adds one item, or a few, to the mask. The order is the increasing order of the mask value, because adding a bit always makes the number bigger. Those three parts are enough to count the work, and the count is the first thing to write down.

Worked example: assigning orders to bakers

Problem. There are n bakers and n orders, with n at most 20. Baker i bakes order j for cost[i][j], or cannot if the cost is -1. Each baker bakes exactly one order and each order is baked by one baker. Find the smallest total cost.

The state. Let dp[mask] be the smallest cost for the first popcount(mask) bakers to bake exactly the orders in mask. Baker number popcount(mask) is the next one to assign, because the bakers are taken in order 0, 1, 2 and so on. The state says nothing about which baker did which order, only the total, and that is enough.

The transition. From dp[mask], take the next baker b = popcount(mask). For each order j that is not in mask and has a cost for b, set

dp[mask | (1 << j)] = the smaller of its current value and dp[mask] + cost[b][j]

The base case is dp[0] = 0. The answer is dp[all], where all = 2^n - 1 is the mask with every order set.

The order. A transition always moves to a bigger mask, so visiting the masks in increasing order is safe. Every mask is final before the code reads it.

The count. There are 2^n masks, and each has up to n transitions. The total is n * 2^n. For n = 20 that is 20,971,520 transitions, about 2 * 10^7. This count is the number to compare with a limit, and it is written down before the code. On random costs the program took 0.008 s for n = 16, 0.018 s for n = 18 and 0.077 s for n = 20, on the machine described in the next section.

The code

// Lesson 02: n bakers and n orders. Each baker takes exactly one order and each order goes to one baker.
// cost[i][j] is the price for baker i to do order j, or -1 if baker i cannot do it.
// dp[mask] = cheapest way for the first popcount(mask) bakers to finish exactly the orders in mask.
// Time O(2^n * n), memory O(2^n).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<ll>> cost(n, vector<ll>(n));
    for (auto &row : cost)
        for (auto &x : row) cin >> x;
 
    const int full = 1 << n;
    vector<ll> dp(full, INF);
    vector<int> lastOrder(full, -1);  // the order added last to reach this mask
    dp[0] = 0;
 
    for (int mask = 0; mask < full; mask++) {
        if (dp[mask] == INF) continue;
        int baker = __builtin_popcount(mask);  // the next baker to assign
        if (baker == n) continue;
        for (int j = 0; j < n; j++) {
            if ((mask >> j) & 1) continue;
            if (cost[baker][j] < 0) continue;
            int nm = mask | (1 << j);  // nm > mask, so increasing mask order is safe
            ll c = dp[mask] + cost[baker][j];
            if (c < dp[nm]) {
                dp[nm] = c;
                lastOrder[nm] = j;
            }
        }
    }
 
    int all = full - 1;
    if (dp[all] == INF) {
        cout << -1 << "\n";
        return 0;
    }
    cout << dp[all] << "\n";
 
    // Walk back: the last order added was lastOrder[mask]; the baker who took it is popcount(prev) of the previous mask.
    vector<int> takenBy(n, -1);
    int mask = all;
    while (mask != 0) {
        int j = lastOrder[mask];
        int prev = mask ^ (1 << j);
        int baker = __builtin_popcount(prev);
        takenBy[baker] = j;
        mask = prev;
    }
    for (int i = 0; i < n; i++) cout << takenBy[i] << (i + 1 < n ? ' ' : '\n');
    return 0;
}

Output on the sample 3 and the rows 1 2 3, 2 4 6, 3 6 9:

10
2 1 0

Baker 0 bakes order 2 for 3, baker 1 bakes order 1 for 4, and baker 2 bakes order 0 for 3. The total is 10.

Check it against a brute force

The brute force tries every permutation of the orders, which is n! choices, so it is for n up to 8. The C++ version in the test does exactly that with next_permutation. The DP and the brute force were compared on 800 random inputs with n from 1 to 7, costs from 0 to 9, and about 20 percent of the cells set to -1. They agreed on every input. For each DP answer the test also checked that the printed assignment is a permutation, uses only allowed cells, and costs what the DP says. These checks ran on the same machine as the timings below. They show the code is right for these sizes, not for every input.

Subsets of a set: enumeration and the trade-off

A common task is to combine the submasks of every mask. For each mask m, the submasks are the masks s with s & ~m = 0. There is a standard loop that visits exactly the submasks of m, starting at m and stepping down with s = (s - 1) & m. It stops after s = 0:

for (int s = mask;; s = (s - 1) & mask) {
    total += f[s];
    if (s == 0) break;
}

Each step leaves only the bits of mask set, so the loop visits each submask once. Why does this count submasks? Each bit of the full set has three options: not in mask, in mask but not in s, or in both. For n bits, that gives 3^n pairs (s, mask) with s a submask of mask. Here is the count for n = 3, with an exact enumeration:

Python · editable

Output:

Enumerating all submasks of every mask is therefore O(3^n). For n = 20 that is 3,486,784,401 pairs, far too many for a typical limit. The other way is sum over subsets: process one bit at a time. After handling bits 0 to b, g[mask] holds the sum over the submasks that differ from mask only in bits 0 to b. Each bit needs one pass over all 2^n masks, so the total is O(2^n * n):

g = f;
for (int b = 0; b < n; b++)
    for (int mask = 0; mask < full; mask++)
        if ((mask >> b) & 1) g[mask] += g[mask ^ (1 << b)];

The two methods give the same output. The program that holds both was compared on random inputs with n up to 6 against a direct double loop, and on n = 12 to 20 the enumeration and the sum over subsets printed the same output (the same SHA-1 hash of the output). The timing on the machine described below:

n	enumeration, O(3^n)	sum over subsets, O(2^n n)
12	0.003 s	0.003 s
14	0.007 s	0.006 s
16	0.033 s	0.009 s
18	0.306 s	0.029 s
20	3.772 s	0.141 s

The table is from one machine: 12 hardware threads, Linux under WSL2, g++ 15.2.0 with -O2 -std=c++17. The times include starting the program and reading the input. Your numbers will differ, but the ratio grows with n: 3^n over 2^n n is 82 at n = 18 and about 166 at n = 20.

The lesson is the count, not the timing. Before you write a loop over submasks, multiply the number of masks by the work per mask. If the total is 3^n and n is near 20, look for a transform that does one pass per bit.

Broken profile: a grid one cell at a time

A grid of W columns and H rows has W * H cells, and 2^(W * H) subsets. For a grid that is wide but short, the number of columns is what matters. A broken profile DP visits the cells one by one, row by row, and keeps one bit per column: the status of the latest cell seen in that column. When the DP is at cell (r, c), bit c is the cell above it and bit c - 1 is the cell to its left, which is already updated. The name comes from the boundary: while the scan is inside a row, the boundary is partly the current row and partly the row above.

Here is the problem. Count the subsets of cells of a W by H grid in which no two chosen cells share a side. The empty subset counts. The state is the mask of the last W cells, which has 2^W values, and there are W * H cells, so the time is W * H * 2^W.

// Lesson 02: broken profile DP. Count the subsets of cells of a W x H grid in which no two chosen
// cells share a side (horizontal or vertical neighbours). The empty subset counts.
// Input: W H. Time O(W * H * 2^W), memory O(2^W).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
    int W, H;
    cin >> W >> H;
    const int full = 1 << W;
    vector<ll> dp(full, 0), nd(full, 0);
    dp[0] = 1;  // before the first cell, no cell is chosen in any column
 
    // Cells are visited row by row. Bit c of the mask is the status of the latest cell seen in column c:
    // the cell above the current one when we are at (r, c), and the cell to the left once c-1 is done.
    for (int r = 0; r < H; r++) {
        for (int c = 0; c < W; c++) {
            fill(nd.begin(), nd.end(), 0);
            for (int mask = 0; mask < full; mask++) {
                if (dp[mask] == 0) continue;
                // Skip the cell: bit c becomes 0.
                nd[mask & ~(1 << c)] += dp[mask];
                // Take the cell: allowed only if the cell above and the cell to the left are not taken.
                bool aboveFree = !((mask >> c) & 1);
                bool leftFree = (c == 0) || !((mask >> (c - 1)) & 1);
                if (aboveFree && leftFree) nd[mask | (1 << c)] += dp[mask];
            }
            swap(dp, nd);
        }
    }
    ll total = 0;
    for (ll x : dp) total += x;
    cout << total << "\n";
    return 0;
}

Outputs: 2 2 gives 7, 3 2 gives 17, and 3 3 gives 63. The 2 by 2 answer can be checked by hand: the empty set, the four single cells, and the two diagonal pairs, which is 1 + 4 + 2 = 7. The 3 by 2 answer of 17 is also hand-checkable, by counting the chosen cells: 1 with none, 6 with one, 8 with two non-touching cells, and 2 with three. A brute force over all 2^16 subsets also gives 1234 for the 4 by 4 grid. The random check covered 60 grids with W and H between 1 and 4.

Common mistakes

Forgetting the forbidden cells. If the check if (cost[baker][j] < 0) continue; is removed, the -1 values are added as costs. On the sample 3 / 1 -1 3 / 2 4 6 / 3 6 9, the correct answer is 10, and the variant without the check prints 8, because it uses the -1 as a negative cost.
Forgetting the left neighbour in the broken profile. If the check leftFree is removed, two cells side by side can both be taken. On the 2 by 2 grid the correct answer is 7, and the variant without the check prints 9.
Submask loops without the stop. If if (s == 0) break; is missing, the loop never ends. When s is 0, the next value is (0 - 1) & mask, which equals mask, so the loop returns to the start and repeats forever. I did not run this case, but the arithmetic shows it.
Memory of 2^n values. For n = 25 an array of 2^25 long long values takes 2^25 * 8 = 268,435,456 bytes, about 256 MiB. Check the memory limit before you raise n. In the assignment DP, the arrays are dp and lastOrder, and for n = 20 they are each about 8 MB and 4 MB.
Using popcount as the baker index when the numbers differ. In the assignment DP, baker = popcount(mask) is correct only because every baker takes exactly one order. If there are fewer orders than bakers, a baker may take nothing, so popcount(mask) no longer says which baker is next. The practice problem below handles that case.

Checklist

Write what the mask means, as a sentence about a set, before any code.
Count the masks (2^n) and the work per mask, and multiply.
Check that every transition moves to a bigger mask, or pick another order.
For submasks, count 3^n for the enumeration and n * 2^n for the sum over subsets, then choose by the limit.
For a grid, write the profile in words: which cell does each bit hold at each step?
Test against a brute force on small random inputs, including the forbidden or invalid cases.
Check the memory for the largest n in the limits.

Summary

A bitmask is a cheap way to store a set, and a DP over masks costs the number of masks times the work per mask. The assignment DP does n steps per mask, so it is O(n 2^n). Enumerating submasks costs 3^n in total, while the sum over subsets costs n 2^n, and the difference is large at n = 20. A broken profile uses one bit per column to walk a grid cell by cell.

Practice

Count the pairs by hand. For n = 2, list every pair (s, mask) where s is a submask of mask. Check your list against the count 3^n.

Show the answer

Answer: 9 pairs. Mask 0 has 1 submask (0), masks 1 and 2 have 2 each (0 and the mask itself), and mask 3 has 4 (0, 1, 2 and 3). The total is 1 + 2 + 2 + 4 = 9, which is 3^2.

Hint: for each mask, count its submasks as 2 to the power of its popcount. Then add the four results.

Submask maximum. Given n at most 16 and 2^n values f[s], print for each mask the largest f[s] over all submasks s of the mask. Write the sum over subsets version. Check it on the sample: n = 2, f = 1 5 3 4.

Show the answer

Answer: change the addition in the sum over subsets to a maximum, since a maximum over submasks also goes one bit at a time. This is the code, which was checked against a direct computation on 300 random inputs:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main(int argc, char **argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string method = argc > 1 ? argv[1] : "sos";
    int n;
    cin >> n;
    int full = 1 << n;
    vector<ll> f(full);
    for (auto &x : f) cin >> x;
    vector<ll> g(full, LLONG_MIN);
 
    if (method == "enum") {
        for (int mask = 0; mask < full; mask++)
            for (int s = mask;; s = (s - 1) & mask) {
                g[mask] = max(g[mask], f[s]);
                if (s == 0) break;
            }
    } else {
        g = f;
        for (int b = 0; b < n; b++)
            for (int mask = 0; mask < full; mask++)
                if ((mask >> b) & 1) g[mask] = max(g[mask], g[mask ^ (1 << b)]);
    }
    for (int mask = 0; mask < full; mask++) cout << g[mask] << (mask + 1 < full ? ' ' : '\n');
    return 0;
}

The sample prints 1 5 3 5. Mask 3 has submasks 0, 1, 2 and 3, and the largest value is 5.

Hint: the sum over subsets adds g[mask ^ (1 << b)] to g[mask]. For a maximum, the same pattern works with max. Check that the mask 0 keeps its own value.

Grid by hand. Count the subsets of a 3 by 2 grid (2 rows, 3 columns) in which no two chosen cells share a side. Then check your count with the program in the lesson.

Show the answer

Answer: 17. Count by the number of chosen cells. There is 1 set with none chosen, 6 with one, 8 with two cells that do not touch, and 2 with three, which are the two sets of three cells that do not touch (one of them is the top-left, top-right and bottom-middle cells). The program prints 17 for 3 2.

Hint: label the cells a, b, c on top and d, e, f below, with a above d, and so on. Count the pairs first: there are 15 pairs in all, and 7 of them share a side.

Fewer orders than bakers. Change the assignment problem: n bakers and m orders, with m at most n. Each order goes to one baker and each baker takes at most one order. Give the DP, and check it on this sample: 3 2, then the rows 1 2, 2 4, 3 6. The answer is 4.

Show the answer

Answer: index the mask by orders, not bakers. Process the bakers one at a time: each baker either takes nothing, or takes one order that is not in the mask. A copy of the array keeps the "takes nothing" choice, and the transitions read the old copy, so a baker takes at most one order. The time is O(n * 2^m * m). This is the code, which agreed with a brute force over all injective maps on 600 random inputs:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
 
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> cost(n, vector<ll>(m));
    for (auto &row : cost)
        for (auto &x : row) cin >> x;
 
    const int full = 1 << m;
    vector<ll> dp(full, INF), ndp;
    dp[0] = 0;
    for (int baker = 0; baker < n; baker++) {
        ndp = dp;  // this baker takes nothing
        for (int mask = 0; mask < full; mask++) {
            if (dp[mask] == INF) continue;
            for (int j = 0; j < m; j++) {
                if ((mask >> j) & 1) continue;
                if (cost[baker][j] < 0) continue;
                int nm = mask | (1 << j);
                ndp[nm] = min(ndp[nm], dp[mask] + cost[baker][j]);  // reads dp, so one order per baker
            }
        }
        dp.swap(ndp);
    }
    ll ans = dp[full - 1];
    cout << (ans >= INF ? -1 : ans) << "\n";
    return 0;
}

The sample prints 4: baker 1 takes order 0 for 2, and order 1 goes to baker 0 for 2.

Hint: why does the transition read dp and write ndp? Think about what would happen if it read ndp instead.

Operation count. For n = 18, compute the number of submask pairs for the enumeration, and the number of steps for the sum over subsets. Which is smaller, and by what factor?

Show the answer

Answer: the enumeration has 3^18 = 387,420,489 pairs, and the sum over subsets has 18 * 2^18 = 4,718,592 steps. The enumeration is about 82 times larger.

Hint: the sum over subsets does one addition for each mask and each bit, so the count is n times 2^n. Divide the two numbers to get the factor.