Bitmask Dynamic Programming

March 2026 · 35 min read

Bitmask DP is one of the most powerful techniques in competitive programming. It uses an integer's bits to represent which elements of a set have been "used" or "visited," enabling DP over all possible subsets. If you have $n$ elements with $n \leq 20$, there are $2^n$ subsets, and each fits in a single integer.

Representing Subsets as Integers

// n elements numbered 0 to n-1
// Subset S is an integer where bit i is set iff element i ∈ S

// {0, 2, 4} → 0b10101 = 21
// {1, 3}    → 0b01010 = 10
// {}         → 0b00000 = 0
// {0,1,...,n-1} → (1 << n) - 1 = all bits set

// Operations:
int S = 0;
S |= (1 << i);           // add element i
S &= ~(1 << i);          // remove element i
bool has = (S >> i) & 1; // check if i ∈ S
int size = __builtin_popcount(S);  // |S|

Iterating Over All Subsets

// All subsets of {0, ..., n-1}:
for (int mask = 0; mask < (1 << n); ++mask) {
    // mask represents a subset
}

// All subsets of a given mask M:
for (int sub = M; sub > 0; sub = (sub - 1) & M) {
    // sub is a subset of M
}
// Don't forget sub = 0 (empty set) if needed

// Why this works: (sub - 1) & M gives the next smaller subset of M.
// It "decrements" within the constrained bit positions of M.

Total cost of "for every mask, iterate its subsets" is $O(3^n)$, not $O(4^n)$. Each pair $(\text{sub}, \text{mask})$ with $\text{sub} \subseteq \text{mask}$ is visited exactly once, and there are $3^n$ such pairs (each of the $n$ bits is independently in neither, in mask only, or in both). For $n = 18$ this is ~387M ops — feasible, but tight.

Two practical filters when looping over masks:

// Skip masks whose popcount is wrong for the problem (e.g. choose-k subsets):
for (int mask = 0; mask < (1 << n); ++mask) {
    if (__builtin_popcount(mask) != k) continue;
    // ...
}

// Or enumerate only k-subsets directly with Gosper's hack
// (next k-subset of n bits in O(1)):
//   int c = mask & -mask;
//   int r = mask + c;
//   mask = (((r ^ mask) >> 2) / c) | r;

Travelling Salesman Problem (TSP)

The classic bitmask DP problem. Given $n$ cities and distances between them, find the shortest tour that visits every city exactly once and returns to the start.

// dp[mask][i] = minimum cost to visit the cities in 'mask'
//              ending at city i
// Base: dp[1 << 0][0] = 0 (start at city 0)
// Transition: for each city j not in mask,
//   dp[mask | (1 << j)][j] = min(dp[mask][i] + dist[i][j])

int tsp(vector<vector<int>>& dist) {
    int n = dist.size();
    int full = (1 << n) - 1;
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    dp[1][0] = 0;  // start at city 0

    for (int mask = 1; mask <= full; ++mask) {
        for (int u = 0; u < n; ++u) {
            if (dp[mask][u] == INT_MAX) continue;
            if (!(mask & (1 << u))) continue;

            for (int v = 0; v < n; ++v) {
                if (mask & (1 << v)) continue;  // already visited
                int next = mask | (1 << v);
                dp[next][v] = min(dp[next][v], dp[mask][u] + dist[u][v]);
            }
        }
    }

    // Find minimum tour: visit all, return to start
    int ans = INT_MAX;
    for (int u = 0; u < n; ++u) {
        if (dp[full][u] != INT_MAX) {
            ans = min(ans, dp[full][u] + dist[u][0]);
        }
    }
    return ans;
}
// Time: O(2^n × n^2)
// Space: O(2^n × n)
// Works for n ≤ 20

Assignment Problem

$n$ workers and $n$ tasks. Each worker has a cost for each task. Assign workers to tasks (one-to-one) to minimize total cost.

// dp[mask] = minimum cost to assign tasks in 'mask' to the first popcount(mask) workers
int assignment(vector<vector<int>>& cost) {
    int n = cost.size();
    vector<int> dp(1 << n, INT_MAX);
    dp[0] = 0;

    for (int mask = 0; mask < (1 << n); ++mask) {
        int worker = __builtin_popcount(mask);  // which worker is next
        if (worker >= n) continue;

        for (int task = 0; task < n; ++task) {
            if (mask & (1 << task)) continue;  // task already assigned
            int next = mask | (1 << task);
            dp[next] = min(dp[next], dp[mask] + cost[worker][task]);
        }
    }
    return dp[(1 << n) - 1];
}
// Time: O(2^n × n), Space: O(2^n)

Sum Over Subsets (SOS) DP

Given an array $a$ of $2^n$ values, compute for each mask $m$:

Naive approach: iterate all subsets of every mask = $O(3^n)$. SOS DP does it in $O(n \cdot 2^n)$:

// f[mask] starts as a[mask]
for (int i = 0; i < n; ++i) {
    for (int mask = 0; mask < (1 << n); ++mask) {
        if (mask & (1 << i)) {
            f[mask] += f[mask ^ (1 << i)];
        }
    }
}
// After this, f[mask] = sum of a[sub] for all sub ⊆ mask

Subset Sum / Partition with Bitmasks

For small $n$ (say $n \leq 24$) you can brute-force over every subset and ask "can these elements hit a target sum?" in $O(2^n)$ time. The trick is to walk masks in order so the sum is computed incrementally.

// Does any subset of a[0..n-1] sum to T?
bool subsetSum(vector<int>& a, int T) {
    int n = a.size();
    vector<int> sum(1 << n, 0);
    for (int mask = 1; mask < (1 << n); ++mask) {
        int low = mask & -mask;          // lowest set bit
        int idx = __builtin_ctz(low);    // its index
        sum[mask] = sum[mask ^ low] + a[idx];
        if (sum[mask] == T) return true;
    }
    return T == 0;
}
// O(2^n) time and space. For n > ~26, switch to meet-in-the-middle (2^(n/2)).

Partition into k equal-sum subsets (LC 698) is a classic bitmask DP: dp[mask] = remaining capacity of the current bucket after assigning the elements in mask; transition by trying to add each unset bit if it fits.

Profile DP (Broken Profile)

Used for grid problems like tiling a grid with dominoes. A bitmask encodes the "profile" of the boundary between the processed and unprocessed parts of the grid. We cover the approach conceptually here:

// State: dp[col][mask]
// mask encodes which cells in the current column boundary are already
// filled by horizontal dominoes from the previous column
// Transition: place vertical and horizontal dominoes to fill column

// Example: tiling an m×n grid with 1×2 dominoes
// dp[0][(1 << m) - 1] = 1 (base: first column fully covered)
// For each column, enumerate valid profile transitions

Complexity Guidelines

Summary

• Subsets of $n$ elements map to $n$-bit integers. Set operations become bitwise operations.
• Iterate subsets of a mask: for(s=M; s>0; s=(s-1)&M).
• TSP: dp[mask][i] = shortest path visiting mask ending at i. $O(2^n n^2)$.
• Assignment: dp[mask] = cost of assigning popcount(mask) workers. $O(2^n n)$.
• SOS DP: Compute $\sum_{s \subseteq m} a[s]$ for all masks in $O(n \cdot 2^n)$.
• Practical limit: $n \leq 20$ for most bitmask DP problems.

Practice Problems

Order is roughly easy → hard. All are bitmask DP unless noted; budget your state at $2^n \cdot \text{something}$ and confirm $n \leq 20$ or so.

1. LC 526 — Beautiful Arrangement medium dp[mask] = arrangements using positions in mask.
2. LC 698 — Partition to K Equal Sum Subsets medium dp[mask] = remaining bucket capacity.
3. LC 1255 — Maximum Score Words hard iterate every subset of words, check letter budget.
4. LC 1986 — Minimum Work Sessions medium SOS-style: precompute which subsets fit in one session.
5. LC 1494 — Parallel Courses II hard dp[mask] over taken courses; iterate $k$-subsets of available.
6. LC 1601 — Maximum Achievable Transfer Requests hard brute over $2^{16}$ request subsets, balance check.
7. LC 943 — Find the Shortest Superstring hard textbook TSP: dp[mask][i] with overlap-cost edges.
8. CSES — Hamiltonian Flights medium count Hamiltonian paths from 1 to n with TSP-style DP.
9. CSES — Counting Tilings hard classic broken-profile DP for $1\times 2$ dominoes on an $n\times m$ grid.
10. Codeforces 449D — Jzzhu and Numbers hard SOS DP on the AND-zero condition with inclusion–exclusion.