Bitmask DP

The state includes a subset, represented as an integer whose bits mark membership. Feasible up to $n\approx 20$-$22$.

Budget

Complexity	Feasible $n$
$O(2^n)$	25
$O(2^{n}n)$	22-23
$O(2^n{n}^2)$	18-20
$O(3^n)$ (submask enumeration)	15-17
$O(2^{n}n)$ memory	20 (memory is usually the binding constraint)

The idioms

mask & (1 << i)            // is i in the set
mask | (1 << i)            // add i
mask & ~(1 << i)           // remove i
mask ^ (1 << i)            // toggle i
__builtin_popcount(mask)   // size of the set
__builtin_ctz(mask)        // index of the lowest set bit
mask & (mask - 1)          // remove the lowest set bit
mask & (-mask)             // isolate the lowest set bit
(1 << n) - 1               // the full set
full ^ mask                // complement

Iterating submasks — $O(3^n)$ total

for (int sub = mask; sub; sub = (sub - 1) & mask) { /* sub is a proper submask */ }
// include the empty submask by handling sub = 0 separately

Summed over all masks this is $3^n$, because each element is in the submask, in the mask-but-not-submask, or in neither. See Enumerating Submasks.

The classic problems

Assignment / minimum cost matching

dp[mask] = minimum cost to assign the first popcount(mask) people to the job set mask.

for (int mask = 0; mask < (1 << n); mask++) {
    int i = __builtin_popcount(mask);            // next person to assign
    if (i == n) continue;
    for (int j = 0; j < n; j++)
        if (!(mask >> j & 1))
            dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + cost[i][j]);
}

$O(2^{n}n)$. Using popcount to derive the row index removes a whole dimension — a trick worth reusing.

TSP / Hamiltonian path

dp[mask][i] = shortest path visiting exactly mask, ending at $i$. $O(2^n{n}^2)$.

Set cover / partition into groups

dp[mask] = minimum groups covering mask; iterate submasks that form a valid group. $O(3^n)$.

for (int mask = 1; mask < (1 << n); mask++)
    for (int sub = mask; sub; sub = (sub - 1) & mask)
        if (valid[sub]) dp[mask] = min(dp[mask], dp[mask ^ sub] + 1);

Counting perfect matchings in a bipartite graph

dp[mask] where the bit count gives the left vertex being matched — this is the permanent, computable in $O(2^{n}n)$ rather than $n!$.

Optimisations

Technique	Gain
Derive one dimension from popcount	removes a factor of $n$ from the state
Iterate submasks	$4^n\to 3^n$
SOS DP	$3^n\to 2^{n}n$ for subset-sum-over-subsets
Only the lowest unset bit matters	when items are interchangeable, forces a canonical order and cuts the branching
Meet in the middle	$2^n\to 2^{n/2}$ when the problem splits
Symmetry breaking	fix that element 0 is in the first group
vector<int> instead of 2D	better cache behaviour at $2^{20}$ states

The “lowest unset bit” trick is underused: in set-partitioning problems, always assign the smallest unassigned element next. This avoids generating the same partition in $k!$ different orders.

Memory

$2^{20}\times 20$ int is 80 MB — usually over the limit. Options: use int not long long, process masks in increasing popcount and keep only the needed layers, or switch to the inclusion-exclusion formulation which is $O(2^n{n}^2)$ time and $O(n^2)$ space.

When $n$ is just too big

• $n\le 40$: meet in the middle
• $n\le 100$, but the graph is sparse: try broken profile DP or tree decomposition
• The subsets have structure (intervals, prefixes): the “subset” dimension may collapse to a number
• Approximate answers acceptable: simulated annealing

See also: Subset DP · SOS DP · Held-Karp