DPAlgorithmaka subset DP, DP over subsets, Held-Karp

Bitmask DP

State is a bitmask encoding which of n ≤ ~20 elements are used, plus optionally the last element; transitions add one bit.

▶ VisualizePattern: Dynamic ProgrammingPractice (2)
Progress

Overview

When the "history" that matters is which elements have been used and n is small (≤ 20–22), encode that set as an integer bitmask: bit i set means element i is used. There are 2^n masks, so tables of size 2^n or 2^n · n fit in memory (2^20 · 20 ≈ 2·10^7). Transitions add one bit (mask | (1 << i)), so the natural order is increasing mask value — every predecessor is numerically smaller.

The flagship is Held-Karp for the Travelling Salesman Problem: dp[mask][v] = shortest path that visits exactly the cities in mask and ends at v, O(2^n · n²) — for n = 16 that is 16.7 million transitions, versus 15! ≈ 1.3·10^12 permutations. Others: assignment problems (dp[mask] = min cost assigning the first popcount(mask) workers to the jobs in mask), Shortest Path Visiting All Nodes (BFS over (mask, node)), partition into k equal-sum subsets, counting Hamiltonian paths, and sum-over-subsets (SOS) DP for aggregating over all submasks in O(2^n · n).

Bit tricks used constantly: mask & (1 << i) test, mask ^ (1 << i) remove, mask & -mask lowest set bit, sub = (sub - 1) & mask to enumerate submasks (total 3^n over all masks). See Bit Masks and Subset Generation with Bitmasks.

bitmasksubsetsO(2^n · n)TSPassignmentn ≤ 20

Intuition

A mental model before the formal terms.

A row of n light switches records which tasks are done. The table has one cell per switch pattern (and, for path problems, per "where I am standing"). To fill a cell you look at patterns with exactly one fewer light on — the pattern you were in just before flipping the last switch. Since flipping a switch on always increases the binary number, filling cells in numeric order is safe.

The exponential is unavoidable — you are genuinely tracking all subsets — but 2^n subsets is enormously smaller than n! orderings, and that gap is what makes n = 20 feasible.

How it works

  1. State: dp[mask] or dp[mask][last]. mask = set of used elements; last = the element that will constrain the next step (current city, last job) when the transition cost depends on it.
  2. Transition: for each unset bit j of mask: dp[mask | 1<<j][j] = best(dp[mask][last] + cost(last, j)). Or, pulling: dp[mask][j] = best over last in mask\{j} of dp[mask ^ 1<<j][last] + cost(last, j).
  3. Base cases: dp[1 << start][start] = 0; everything else INF (or 0 for counting). For assignment, dp[0] = 0.
  4. Order: increasing mask (transitions only add bits). Table: flat arrays of size 2^n or 2^n × n. Answer: dp[full][*] combined as required (e.g. plus return edge for TSP tour).
  5. Optimization: when the transition depends only on popcount(mask) (assignment), drop the second index; use int32 arrays; prune masks that are unreachable.

Why it works

Two partial tours that visited the same set of cities and end in the same city have identical futures — the remaining cities and the current position are all that matters. So (mask, last) is a complete state, and only the best value per state needs to be kept.

Since mask | bit > mask, increasing numeric order is a topological order of the state DAG, and each of the 2^n · n states does O(n) work.

Recognition

How to tell a problem wants this.

  • n ≤ 20 (occasionally 22–24) with a problem that is otherwise about permutations, subsets, or assignments — the constraint is the tell.
  • "Visit every node", "assign each task to a distinct worker", "partition into groups", "count subsets with property".
  • A brute force would enumerate orderings (n!) but only the set of used items matters for the future.
“number of ways” → Dynamic Programming“parity/odd occurrences” → Bit Manipulation

Interactive visualization

Play, step, change the input. ← → and space work too.

end 0end 1end 2end 3
0000∞∞∞∞
00010∞∞∞
0010∞∞∞∞
0011∞∞∞∞
0100∞∞∞∞
0101∞∞∞∞
0110∞∞∞∞
0111∞∞∞∞
1000∞∞∞∞
1001∞∞∞∞
1010∞∞∞∞
1011∞∞∞∞
1100∞∞∞∞
1101∞∞∞∞
1110∞∞∞∞
1111∞∞∞∞
1/17dp[mask][u] = shortest path that visits exactly the nodes in mask (bit i = node i, shown as a binary string, low bit rightmost) and ends at u. Start: only node 0 visited, cost 0.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Bitmask DP →
1dp[1][0] = 0            // visited {0}, ending at 0
2for mask in increasing order, for u in mask with dp[mask][u] < ∞:
3  for v not in mask:
4    dp[mask | 1<<v][v] = min(dp[mask | 1<<v][v], dp[mask][u] + d[u][v])
5answer = min over u of dp[FULL][u] + d[u][0]
Variables
n4
masks16
Complexity
worst O(2^n · n²) for TSP-style (mask, last) states; O(2^n · n) for dp[mask] with one-bit transitions; O(3^n) for submask enumeration
space O(2^n · n) or O(2^n)
Speed

Pseudocode

1# TSP (Held-Karp): dp[mask][v] = min cost path visiting mask, ending at v
2dp[1 << 0][0] = 0; all else INF
3for mask in 1..2^n - 1:
4  for v in mask:
5    if dp[mask][v] == INF: continue
6    for u not in mask:
7      dp[mask | 1<<u][u] = min(dp[mask | 1<<u][u], dp[mask][v] + dist[v][u])
8return min over v of dp[full][v] + dist[v][0]

Implementations

1import math
2 
3# Bitmask DP: when the state is "which subset of a small set have I used",
4# encode that subset as the bits of an integer. n up to about 20 is the
5# practical ceiling (2^20 states). Representative example: assignment problem
6# (n tasks to n workers at minimum cost), plus Held-Karp for the TSP.
7 
8 
91 · dp[mask] = min cost to assign the first popcount(mask) workers to the
10# tasks in mask. The worker index is implied by how many bits are set.
11def min_assignment_cost(cost: list[list[int]]) -> float:
12    n = len(cost)
13    full = 1 << n
14    dp = [math.inf] * full
15    dp[0] = 0
16 
17    for mask in range(full):
18        if dp[mask] == math.inf:
19            continue
20        worker = bin(mask).count("1")  # next worker to assign (int.bit_count in 3.10+)
21        if worker == n:
22            continue
232 · Try every still-free task for this worker
24        row = cost[worker]
25        for task in range(n):
26            if mask & (1 << task):
27                continue  # already taken
28            nxt = mask | (1 << task)
29            if dp[mask] + row[task] < dp[nxt]:
30                dp[nxt] = dp[mask] + row[task]
31    return dp[full - 1]
32 
33 
343 · Held-Karp: dp[mask][last] = shortest path visiting mask, ending at last
35def tsp(dist: list[list[int]]) -> float:
36    n = len(dist)
37    if n == 0:
38        return 0
39    full = 1 << n
40    dp = [[math.inf] * n for _ in range(full)]
41    dp[1][0] = 0  # start at city 0
42 
43    for mask in range(1, full):
44        if not mask & 1:
45            continue  # every tour includes city 0
46        row = dp[mask]
47        for last in range(n):
48            if not mask & (1 << last) or row[last] == math.inf:
49                continue
504 · Extend the path to any unvisited city
51            base = row[last]
52            dist_last = dist[last]
53            for nxt in range(n):
54                if mask & (1 << nxt):
55                    continue
56                nm = mask | (1 << nxt)
57                if base + dist_last[nxt] < dp[nm][nxt]:
58                    dp[nm][nxt] = base + dist_last[nxt]
59 
605 · Close the tour by returning to city 0
61    if n == 1:
62        return 0
63    return min(
64        (dp[full - 1][last] + dist[last][0] for last in range(1, n) if dp[full - 1][last] < math.inf),
65        default=math.inf,
66    )
Walkthrough
  1. bin(mask).count("1") is the portable population count; int.bit_count() is the fast built-in from Python 3.10 and is noted in the comment.
  2. Python integers are unbounded, so 1 << n is exact for any n — the only limit is memory for 2^n states, not the word size.
  3. row = cost[worker], base = row[last] and dist_last = dist[last] hoist repeated lookups out of the innermost loop, which matters a lot in CPython.
  4. The explicit if base + d < dp[nm][nxt] comparison instead of min(...) avoids a function call in the hot loop.
  5. min(generator, default=math.inf) handles the case where no tour completes, without a separate emptiness check.
Complexity (this implementation)
time O(2^n * n) for the assignment problem; O(2^n * n^2) for Held-Karp · space O(2^n) and O(2^n * n) respectively

Python is roughly 50x slower than C++ here, so the practical ceiling drops to about n = 15 rather than n = 20.

Language notes
  • int.bit_count() (3.10+) is a single fast call; bin(x).count("1") builds a string and is much slower in a hot loop.
  • Python integers are arbitrary precision, so bit masks never overflow — the one language here with no shift-width limit.
  • min(gen, default=...) is the clean way to handle a possibly-empty minimisation.
  • scipy.optimize.linear_sum_assignment solves the assignment problem in O(n^3) via the Hungarian algorithm and should be used for anything but a demonstration.
Common mistakes in this language
  • Using bin(mask).count("1") inside the innermost loop rather than once per mask.
  • Calling min() in the hot loop instead of an explicit comparison, which adds a Python-level call per candidate.
  • Reaching for bitmask DP on the assignment problem at all, when scipy solves it in polynomial time.
Language differences that matter here
  • Population count: C++ has __builtin_popcount / std::popcount, Python has int.bit_count() (3.10+), and JS/TS have nothing — the Kernighan loop is written out there.
  • Shift width: Python integers are unbounded, C++ int shifts are undefined behaviour at 31+, and JS/TS bitwise operators silently coerce to signed int32 — the same expression has three different failure modes.
  • The unreachable sentinel: Infinity and math.inf saturate safely under addition, while C++ needs INT_MAX / 4 headroom to avoid overflowing before the guard runs.
  • Only Python has a library escape hatch (scipy.optimize.linear_sum_assignment) that makes the assignment problem polynomial rather than exponential.

Complexity

Best
—
Average
—
Worst
O(2^n · n²) for TSP-style (mask, last) states; O(2^n · n) for dp[mask] with one-bit transitions; O(3^n) for submask enumeration
Space
O(2^n · n) or O(2^n)

n = 20 → 2^20 ≈ 10^6 masks; n = 16 with n² transitions ≈ 1.7·10^7 operations.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • n ≤ 20 and the future depends only on the set of used elements (plus possibly the last one).
  • Hamiltonian path/cycle, assignment, set partition, "visit all" problems.
  • Aggregating a function over all subsets or all submasks (SOS DP).
Avoid it when
  • n > 25 — 2^n is infeasible; look for structure (greedy, matching, flow, meet-in-the-middle for n ≤ 40).
  • Only the count of used elements matters, not which — a plain 1D/2D DP suffices.
  • The problem is an assignment with a bipartite structure and large n — use the Hungarian algorithm or min-cost flow instead.

Alternatives

Subsets (Power Set)PermutationsSubset Generation with BitmasksState Machine DPBreadth-First Search (BFS)

Common mistakes

  • Iterating masks in an order that is not topological for the transition used (e.g. removing bits while iterating upward).
  • Allocating dp[2^n][n] with 64-bit values for n = 20 (160 MB) — use 32-bit or drop a dimension.
  • Off-by-one on 1 << n vs (1 << n) - 1; forgetting the start-city bit in the initial mask.
  • Using INF sums that overflow 32-bit ints when adding costs; use INF = 1e9, not INT_MAX.
  • Mixing up "in mask" tests: (mask >> i) & 1 vs mask & i.

Interview patterns

  • Shortest Path Visiting All Nodes (BFS on (mask, node)).
  • Assignment / "Minimum Cost to Assign Jobs", Campus Bikes II, Number of Ways to Wear Different Hats.
  • Partition to K Equal Sum Subsets, Matchsticks to Square (dp[mask] with running remainder).
  • Count Hamiltonian paths; Parallel Courses II (submask enumeration).
Interview questions on this
Mock interviews

Example problems

Shortest Path Visiting All NodeshardSubsetsmedium