Pattern Reference
Bitmask DP
"DP over subsets using bitmasks. TSP, assignment, graph covering, state space search."
Loading...
Deep Dive Tutorial
Bitmask DP represents a subset of n elements as a single integer where bit k = 1 means element k is included. With n ≤ 20, there are 2^n ≈ 1M subsets — manageable with DP. The key insight: transitions between subsets are fast bitwise operations. Classic signals: "visit all cities exactly once," "assign tasks to workers," "cover all requirements."
| Operation | Code | Meaning |
|---|---|---|
| Check if bit k set | (mask >> k) & 1 | Is element k in subset? |
| Add element k | mask | (1 << k) | Include k in subset |
| Remove element k | mask & ~(1 << k) | Exclude k from subset |
| All n elements | (1 << n) - 1 | Full set bitmask |
| Enumerate subsets of mask | for(s=mask; s>0; s=(s-1)&mask) | All non-empty subsets |
| Count set bits | Integer.bitCount or loop n&(n-1) | Size of subset |
Core Template: dp[mask] = best for subset "mask"
Bitmask DP template — visiting all nodes
// dp[mask][i] = best cost to have visited exactly the nodes in mask,
// ending at node i
// mask has bit i set iff we've visited node i
const n = /* number of nodes */;
const INF = Infinity;
const dp = Array.from({length: 1<<n}, () => new Array(n).fill(INF));
// Base: start at node 0, only node 0 visited
dp[1][0] = 0; // mask = 0001 (only bit 0 set), at node 0, cost 0
for (let mask = 1; mask < (1<<n); mask++) {
for (let u = 0; u < n; u++) {
if (!(mask >> u & 1)) continue; // u not in this mask
if (dp[mask][u] === INF) continue;
for (let v = 0; v < n; v++) {
if (mask >> v & 1) continue; // v already visited
const newMask = mask | (1 << v);
dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + cost[u][v]);
}
}
}
// Answer: visit all nodes (full mask), end anywhere
const fullMask = (1<<n) - 1;
return Math.min(...dp[fullMask]);Subset Enumeration Trick
Enumerate all subsets of a bitmask
// Enumerate all non-empty subsets of 'mask' in O(3^n) total
for (let s = mask; s > 0; s = (s - 1) & mask) {
// process subset s of mask
// (s-1) & mask clears the lowest set bit of s and
// removes all bits not in mask
}
// Example: split mask into two complementary parts
for (let s = mask; s > 0; s = (s-1) & mask) {
const complement = mask ^ s; // mask XOR s = bits in mask but not in s
dp[mask] = Math.min(dp[mask], f(s) + f(complement));
if (s === 0) break; // handle s=0 separately if needed
}
// Why O(3^n)? Each element is in: mask but not s, mask and s, or not in mask
// → 3 choices per element → 3^n total work across all masksWorked Problems
brain
Bitmask DP signals:
- "Visit/cover all n elements" where n ≤ 20 → bitmask DP
- "Assign each item from set A to one from set B" → bitmask on one set
- "Minimum cost partition into subsets" → dp[mask] = min over splits
- "State includes which elements chosen" → encode as bitmask
Subset enumeration:
Space optimization: if only previous-mask states needed, use 1D dp[mask] iterated in correct order.
- "Visit/cover all n elements" where n ≤ 20 → bitmask DP
- "Assign each item from set A to one from set B" → bitmask on one set
- "Minimum cost partition into subsets" → dp[mask] = min over splits
- "State includes which elements chosen" → encode as bitmask
Subset enumeration:
for(s=mask; s>0; s=(s-1)&mask) — O(2^popcount(mask)) per mask, O(3^n) total.Space optimization: if only previous-mask states needed, use 1D dp[mask] iterated in correct order.