← All patternsBitmask DP · template
Pattern · Dynamic Programming
Bitmask DP
Represent which items are used as the bits of an integer, so dp[mask] covers every subset (n up to about 20).
Time O(2^n × n²) · Space O(2^n × n)
Taught in Module 32: Advanced DP
Think of it like this
A row of light switches, one per city visited: every on/off pattern is one state in the table.
Clues that point here
- → Small n (≤ 20) with "visit all" or "assign each"
- → Travelling salesman
- → Partition into k equal subsets
- → Assignment problems
Not this pattern when
- ✕ n is large (2^n states won't fit)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
int full = (1 << n) - 1;
int[][] dp = new int[1 << n][n]; // dp[mask][last] = best cost
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
dp[1][0] = 0; // start at node 0
for (int mask = 1; mask <= full; mask++)
for (int last = 0; last < n; last++) {
if ((mask & (1 << last)) == 0) continue;
for (int next = 0; next < n; next++) {
if ((mask & (1 << next)) != 0) continue;
int nm = mask | (1 << next);
dp[nm][next] = Math.min(dp[nm][next], dp[mask][last] + cost[last][next]);
}
}Common versions
- Travelling salesman
- Partition to K equal sum subsets
- Shortest path visiting all nodes
- Smallest sufficient team
Practice problems with this pattern
32.8Partition to K Equal Sum SubsetsMediummain pattern32.9Shortest Path Visiting All NodesHardmain pattern