Bitmask DP
A delivery driver has 15 stops. In which order should she visit them to drive the fewest kilometres? There are orders that start at the depot. Checking all of them takes minutes even in fast code. Yet a twenty-line program answers it in a few milliseconds, exactly, with no heuristics. The trick is one sentence: once you are standing somewhere, the order in which you visited the earlier stops no longer matters — only which stops you have visited. There are orders but only sets, and a set of up to about 20 items fits in one machine integer.
That is bitmask DP: dynamic programming where part of the state is a set, stored as the bits of an integer (a bitmask). This lesson builds it from the ground up: how a set becomes a number, the Held–Karp algorithm for the travelling salesman problem (with the actual tour recovered, not just its length), the assignment problem, counting Hamiltonian paths, splitting items into equal groups, packing tasks into work sessions, breadth-first search over (node, mask) pairs, and the trick for looping over every subset of every subset. It ends with honest memory arithmetic: bitmask DP is exponential, and you must know where the wall is.
This lesson assumes DP Foundations (state, transition, base case) and the operators in Bit Manipulation. The Euler & Hamiltonian Paths lesson gave a first taste of the Hamiltonian-path DP; here we go much further.
Why this exists
Many problems ask you to choose an order or an assignment of a small number of things: visit every city once, give every worker one job, put every task into some session, split every number into one of groups. The obvious brute force tries every order: of them. is fine. is not. would take decades.
But most of the information in an order is irrelevant to the future. If you have visited cities and are now at city 2, the cheapest way to finish the tour does not care whether you went or . Only two facts matter: the set of cities already visited and where you are now. Two partial tours with the same set and the same endpoint compete; only the cheaper one can be part of an optimal tour, so we keep one number for each such pair. There are pairs instead of orders. For that is about 21 million instead of .
This idea was published twice in 1962: by Richard Bellman ("Dynamic programming treatment of the travelling salesman problem", Journal of the ACM 9(1)) and by Michael Held and Richard Karp ("A dynamic programming approach to sequencing problems", Journal of the SIAM 10(1)). It is still the fastest known exact worst-case algorithm for the general travelling salesman problem with arbitrary distances — sixty years later, nobody has found an algorithm for that general case (faster algorithms exist for special cases such as bounded-degree graphs or plain Hamiltonicity; see Variations).
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| (or , , ) and "visit every…", "use each exactly once" | Bitmask over the used items |
| "shortest route through all cities and back", "travelling salesman" | Held–Karp: dp[mask][last] |
| " workers, jobs, each worker gets exactly one job", | Assignment DP: dp[mask], worker index = popcount |
| "count the orderings / permutations such that adjacent elements satisfy…" | dp[mask][last] counting version |
| "count Hamiltonian paths", "routes that visit every city once" | dp[mask][v] counting, see Euler & Hamiltonian Paths |
| "divide into groups with equal sum", "fewest bins / sessions / rides of capacity " | dp[mask] storing the load of the currently open group |
| "shortest walk that visits every node" in an unweighted graph, nodes may repeat | BFS over states (node, mask) |
| "split into groups, score depends on the whole group" | Submask enumeration, |
| Grid with columns and cells that interact with the row above | Profile DP: Broken-Profile DP |
| "for every mask, sum / max over all its submasks" | SOS DP, instead of |
| items | Not bitmask DP over all items. Look for meet-in-the-middle, greedy, flow, or Hungarian |
The meta-trigger: a tiny that looks oddly specific. Problem setters choose precisely because . When you see such a limit together with "each item used once", the state almost certainly contains a set.
Intuition & first principles
A set is a number
Number the items . A subset is stored as the integer whose bit is 1 exactly when item is in . With :
| Set | Bits (item 3 on the left) | Integer |
|---|---|---|
0000 | 0 | |
0001 | 1 | |
0101 | 5 | |
1110 | 14 | |
1111 | 15 = |
Every subset of is an integer in , and every such integer is a subset. So "an array indexed by subsets" is just an array of length . The set operations become single CPU instructions:
| Set operation | Bit operation | Example (mask = 0101) |
|---|---|---|
| Is ? | (mask >> i) & 1 | : 1 (yes) |
mask | (1 << i) | : 0111 | |
mask & ~(1 << i) (or mask ^ (1 << i) if ) | : 0100 | |
popcount (bit_count(), Integer.bitCount, __builtin_popcount) | 2 | |
| Smallest element | mask & -mask (lowest set bit) | 0001 |
| Complement within items | full ^ mask, where full = (1 << n) - 1 | 1010 |
| Is ? | (A & B) == A |
Bit Manipulation covers these operators in detail.
Operator precedence
In C, C++, Java and JavaScript, == binds tighter than &. mask & 1 << i == 0 parses as mask & ((1 << i) == 0). Always parenthesise: ((mask >> i) & 1) == 0.
Forget the order, keep the set
Take four cities with these road lengths (symmetric: the same in both directions).
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 10 | 15 | 20 |
| 1 | 10 | 0 | 35 | 25 |
| 2 | 15 | 35 | 0 | 30 |
| 3 | 20 | 25 | 30 | 0 |
Two partial tours, both starting at city 0, both having visited , both standing at city 2:
- : .
- : .
Whatever you do next (here: drive home to 0), you do it from the same city with the same cities left. So the second partial tour can never beat the first. Keep 65, throw 80 away. That is the entire DP. We call the pair (visited set, current city) a state, and we store the best cost of reaching each state.
flowchart LR
P1["0 → 1 → 3 → 2, cost 65"] --> S["state: set 1111, at city 2"]
P2["0 → 3 → 1 → 2, cost 80"] --> S
S -->|"keep only min = 65"| F["any completion: 2 → 0"]
Why increasing numeric order is a valid fill order
A DP needs an order in which every state is finished before anyone reads it. In bitmask DP the transitions almost always add elements to the set: next = mask | (1 << k) with bit not yet in mask. Adding a bit that was 0 makes the integer strictly larger (). So if we process masks in increasing numeric order, every mask is completely finished (all its incoming transitions came from smaller numbers) before we push from it. No topological sort needed: for mask in range(1 << n) is already one.
The same argument shows the state graph is a DAG (a directed graph without cycles), which is why bitmask DP is really a DAG DP on a graph with layers of sets.
The four questions for every bitmask DP
- What is in the set? Visited cities, assigned jobs, used numbers, placed tasks.
- What else must the state remember? The current city (TSP), nothing (assignment: the worker index is the popcount), the load of the open bucket (partition), the current node (BFS).
- What does a transition add? Usually one new element; sometimes a whole group (submask transitions).
- Is the state small enough? cells times bytes per cell must fit in memory, and states times transitions must fit in time. See Feasibility limits.
Mechanics
1. Travelling salesman: Held–Karp
Problem. cities, distance matrix dist. Find the cheapest closed tour that starts at city 0, visits every city exactly once, and returns to 0.
State. dp[mask][j] = the cheapest cost of a path that starts at city 0, visits exactly the cities in mask (which must contain 0 and ), and ends at city .
Base. dp[{0}][0] = 0 — standing at the start, nothing driven.
Transition (push form). From state (mask, j) drive to any unvisited city :
Answer. Close the loop: .
Reconstruction. Store parent[mask][j] = the city we came from when dp[mask][j] was last improved. Walk back from the best final city, removing each city from the mask as you go.
flowchart LR
A["0001 at 0 : 0"] -->|"+10"| B["0011 at 1 : 10"]
A -->|"+15"| C["0101 at 2 : 15"]
A -->|"+20"| D["1001 at 3 : 20"]
C -->|"+30"| E["1101 at 3 : 45"]
E -->|"+25"| F["1111 at 1 : 70"]
F -->|"+10 home"| G["tour cost 80"]
The diagram shows only the states on the winning tour; the real DP fills every reachable state.
Trace on the 4-city example
Masks are written with city 3 on the left. Only masks that contain city 0 are reachable. The table lists every reachable state in the order the DP finalises them, with its value and parent (the previous city).
| Mask | Cities | dp[mask][j] (parent) | How the best value arose |
|---|---|---|---|
0001 | {0} | j=0: 0 (—) | base |
0011 | {0,1} | j=1: 10 (0) | 0 + d(0,1) = 10 |
0101 | {0,2} | j=2: 15 (0) | 0 + d(0,2) = 15 |
1001 | {0,3} | j=3: 20 (0) | 0 + d(0,3) = 20 |
0111 | {0,1,2} | j=1: 50 (2), j=2: 45 (1) | j=1: 15 + 35; j=2: 10 + 35 |
1011 | {0,1,3} | j=1: 45 (3), j=3: 35 (1) | j=1: 20 + 25; j=3: 10 + 25 |
1101 | {0,2,3} | j=2: 50 (3), j=3: 45 (2) | j=2: 20 + 30; j=3: 15 + 30 |
1111 | all | j=1: 70 (3), j=2: 65 (3), j=3: 75 (1) | two candidates each, worked out below |
For the last row, each entry takes the minimum over the two possible previous cities:
dp[1111][1]= min(dp[1101][2]+ 35,dp[1101][3]+ 25) = min(50 + 35, 45 + 25) = 70, parent 3.dp[1111][2]= min(dp[1011][1]+ 35,dp[1011][3]+ 30) = min(45 + 35, 35 + 30) = 65, parent 3.dp[1111][3]= min(dp[0111][1]+ 25,dp[0111][2]+ 30) = min(50 + 25, 45 + 30) = 75, parent 1 (tie with 2; the first one found is kept).
Closing the loop: city 1 gives 70 + 10 = 80, city 2 gives 65 + 15 = 80, city 3 gives 75 + 20 = 95. The optimum is 80 (cities 1 and 2 tie because the two optimal tours are mirror images of each other).
Walking back from city 1 (the first best end):
| Step | Mask | City | Parent | Mask after removing city |
|---|---|---|---|---|
| 1 | 1111 | 1 | 3 | 1101 |
| 2 | 1101 | 3 | 2 | 0101 |
| 3 | 0101 | 2 | 0 | 0001 |
| 4 | 0001 | 0 | — | stop |
Reading the cities in reverse: , cost .
Brute-force check. With city 0 fixed, there are orders of the other cities:
| Order | Cost |
|---|---|
| 0 1 2 3 0 | 95 |
| 0 1 3 2 0 | 80 |
| 0 2 1 3 0 | 95 |
| 0 2 3 1 0 | 80 |
| 0 3 1 2 0 | 95 |
| 0 3 2 1 0 | 95 |
The minimum is 80, matching the DP. The implementation below runs this comparison automatically on hundreds of random instances.
2. The assignment problem: dp[mask] alone
Problem. workers, jobs, cost[i][j] = cost of worker doing job . Give each worker exactly one job (each job to exactly one worker) at minimum total cost.
The key observation. Assign workers in the fixed order . Then after some steps, the set of used jobs tells you everything: if mask has bits set, workers are done and the next worker is . The worker index does not need its own dimension. The state shrinks from to .
State. dp[mask] = the cheapest way to give the first popcount(mask) workers exactly the jobs in mask.
Base. dp[0] = 0.
Transition. With , for each job : dp[mask | 1<<j] = min(…, dp[mask] + cost[i][j]).
Answer. dp[full].
Example, four workers (rows) and four jobs (columns):
| job 0 | job 1 | job 2 | job 3 | |
|---|---|---|---|---|
| worker 0 | 9 | 2 | 7 | 8 |
| worker 1 | 6 | 4 | 3 | 7 |
| worker 2 | 5 | 8 | 1 | 8 |
| worker 3 | 7 | 6 | 9 | 4 |
Trace, layer by layer (a layer = all masks with the same popcount = one worker). "Last job" is the job given to the most recent worker on the best way to reach the mask.
| Layer (worker just assigned) | Mask → dp (last job) |
|---|---|
| 0 (none) | 0000 → 0 |
| 1 (worker 0) | 0001 → 9 (0), 0010 → 2 (1), 0100 → 7 (2), 1000 → 8 (3) |
| 2 (worker 1) | 0011 → 8 (0), 0101 → 12 (2), 0110 → 5 (2), 1001 → 14 (0), 1010 → 9 (3), 1100 → 11 (2) |
| 3 (worker 2) | 0111 → 9 (2), 1011 → 14 (0), 1101 → 15 (2), 1110 → 10 (2) |
| 4 (worker 3) | 1111 → 13 (3) |
Take 0011 → 8: workers 0 and 1 hold jobs {0, 1}. Either worker 0 takes job 0 and worker 1 job 1 (), or worker 0 takes job 1 and worker 1 job 0 (). The DP keeps 8.
Reconstruction. 1111 last job 3 → worker 3 does job 3; remove it: 0111 last job 2 → worker 2 does job 2; 0011 last job 0 → worker 1 does job 0; 0010 last job 1 → worker 0 does job 1. Total . Checking all permutations also gives 13.
Bitmask DP vs the Hungarian algorithm
The Hungarian algorithm solves the same assignment problem in — polynomial, so is fine. The bitmask DP is and dies past . Why learn the DP at all? Because it is ten lines, impossible to get subtly wrong, and it bends: costs that depend on which other jobs are already taken, counting the number of perfect matchings (the Hungarian method cannot count; counting perfect matchings is #P-complete in general, Valiant 1979), "each job can take up to two workers", XOR or other non-additive objectives. When the objective is a plain sum and is large, use Hungarian; when and the problem has a twist, use the DP.
| Bitmask assignment DP | Hungarian (Kuhn–Munkres) | |
|---|---|---|
| Time | ||
| Memory | ||
| Largest practical | about 23–25 | thousands |
| Counts matchings? | Yes (replace min by +) | No |
| Arbitrary set-dependent costs? | Yes | No (needs a sum of independent pair costs) |
| Lines of code | ~10 | ~40–60 |
3. Counting Hamiltonian paths
A Hamiltonian path visits every vertex of a graph exactly once. Deciding whether one exists is NP-complete (Karp, 1972), so no polynomial algorithm is expected. Bitmask DP gives : the TSP table with "+" instead of "min".
ways[mask][v] = number of paths that start at vertex 0, visit exactly mask, and end at v. Base ways[{0}][0] = 1; for each edge with mask, add ways[mask][v] to ways[mask | {w}][w]. The number of Hamiltonian paths from 0 to is ways[full][n-1].
def count_hamiltonian_paths(n, edges, mod=None):
"""Directed paths 0 -> n-1 that visit every vertex exactly once. Parallel edges count separately."""
out = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
full = (1 << n) - 1
ways = [[0] * n for _ in range(1 << n)]
ways[1][0] = 1
for mask in range(1, 1 << n):
if not mask & 1:
continue # every path starts at 0
if (mask >> (n - 1)) & 1 and mask != full:
continue # reached the goal too early: dead state
for v in range(n):
w_count = ways[mask][v]
if w_count == 0:
continue
for w in out[v]:
if not (mask >> w) & 1:
nxt = mask | (1 << w)
ways[nxt][w] += w_count
if mod:
ways[nxt][w] %= mod
return ways[full][n - 1]
# The multigraph from the Euler & Hamiltonian lesson: 0->1 twice, 1->2, 2->3, 0->2, 1->3, 2->1
assert count_hamiltonian_paths(4, [(0, 1), (0, 1), (1, 2), (2, 3), (0, 2), (1, 3), (2, 1)]) == 3
# Complete directed graph on 5 vertices: the 3 middle vertices can come in any order, 3! = 6
assert count_hamiltonian_paths(5, [(a, b) for a in range(5) for b in range(5) if a != b]) == 6
The "skip masks that contain the goal too early" line is the optimisation used in CSES Hamiltonian Flights: a path that reaches before the end can never be extended, so those states are dead. It roughly halves the work. The Euler & Hamiltonian Paths lesson traces this DP state by state.
To detect a Hamiltonian path with any start and end, set ways[{v}][v] = 1 for every , use booleans, and check whether any ways[full][v] is true. A neat speed-up stores, for each mask, a bitmask of possible end vertices: ends[mask] has bit set if some path visits mask and ends at . Then the inner loop over and its edges becomes one AND with an adjacency mask: word operations.
4. Partition into equal-sum subsets
Problem. Can the multiset nums (length ) be split into groups with equal sums?
Let target = sum / k (if it is not an integer, the answer is no). Imagine filling buckets one at a time: you put numbers into the current bucket until it holds exactly target, then you close it and open a new one. The state is the set of numbers used so far. Here is the surprise: the load of the open bucket is determined by the mask. If the numbers in mask sum to , all closed buckets hold target each, so the open bucket holds . So a single boolean per mask suffices: "can the numbers in mask be placed this way without ever overflowing a bucket?"
Transition. From a reachable mask with open load , add any unused number with .
def can_partition_k_subsets(nums, k):
total = sum(nums)
if total % k:
return False
target = total // k
if max(nums) > target:
return False
n = len(nums)
load = [-1] * (1 << n) # load of the open bucket; -1 = unreachable
load[0] = 0
for mask in range(1 << n):
if load[mask] < 0:
continue
for i in range(n):
if (mask >> i) & 1 or load[mask] + nums[i] > target:
continue
load[mask | (1 << i)] = (load[mask] + nums[i]) % target
return load[(1 << n) - 1] == 0
assert can_partition_k_subsets([4, 3, 2, 3, 5, 2, 1], 4) # {5}, {1,4}, {2,3}, {2,3}
assert not can_partition_k_subsets([1, 2, 3, 4], 3) # sum 10 is not divisible by 3
assert not can_partition_k_subsets([2, 2, 2, 2, 3, 4, 5], 4) # target 5, but 4 needs a 1
time, memory. For : about a million steps. The backtracking alternative (try to fill bucket 1, then bucket 2, …) is often faster in practice with good pruning but has no such guarantee.
5. Minimum number of work sessions (bin packing on a mask)
Problem. Tasks take tasks[i] hours ( on LeetCode, in the CSES version Elevator Rides). A work session lasts at most T hours. A task cannot be split. What is the minimum number of sessions?
This is bin packing, NP-hard in general. Generalise the trick from §4: the open session's load is no longer determined by the mask (the closed sessions are not all full), so store it. And store the pair (sessions used, load of the last session), compared lexicographically: fewer sessions is better, and among equal session counts, a lighter last session is better (it has more room).
def min_sessions(tasks, T):
"""Fewest sessions of length <= T that fit all tasks (each task <= T)."""
n = len(tasks)
best = [(n + 1, 0)] * (1 << n) # (sessions opened, load of the last session)
best[0] = (1, 0) # one empty session open
for mask in range(1 << n):
sessions, load = best[mask]
for i in range(n):
if (mask >> i) & 1:
continue
if load + tasks[i] <= T:
cand = (sessions, load + tasks[i]) # fits into the open session
else:
cand = (sessions + 1, tasks[i]) # open a new session
nxt = mask | (1 << i)
if cand < best[nxt]:
best[nxt] = cand
return best[(1 << n) - 1][0]
assert min_sessions([1, 2, 3], 3) == 2
assert min_sessions([3, 1, 3, 1, 1], 8) == 2
assert min_sessions([1, 2, 3, 4, 5], 15) == 1
assert min_sessions([4, 8, 6, 1], 10) == 2 # CSES Elevator Rides sample: {4, 6}, {8, 1}
Why is keeping only the lexicographically smallest pair safe? Suppose two ways of placing the same set of tasks end with . If , then and , so from the first state, any continuation that the second state can do with more sessions, the first can do with at most more sessions (in the worst case open a new session immediately, matching the second's open session which has some load ). If and , the first state's open session has at least as much room, so it can mimic every continuation. Either way the first state is never worse. This "dominance" argument is how you justify storing a pair instead of a full set of options.
6. Shortest path visiting all nodes: BFS over (node, mask)
Problem (LeetCode 847). An undirected, connected, unweighted graph with nodes. Find the length of the shortest walk that visits every node. You may start anywhere, end anywhere, and revisit nodes and edges.
Revisiting is allowed, so this is not a Hamiltonian path, and "increasing mask order" no longer works: moving to an already-visited node leaves the mask unchanged, so transitions can stay inside a mask and even form cycles. But every move costs exactly 1, which is the setting where BFS finds shortest paths in any graph, cycles or not. So run BFS on the state graph: a state is (mask, v) = "I have visited mask and I am at v", and an edge in the original graph becomes the state edge (mask, v) → (mask | {w}, w).
Start BFS from all states ({v}, v) at once (a multi-source BFS, because the start is free). The first time any state with mask == full is popped, its distance is the answer.
flowchart LR
S0["(0001, 0)"] -->|"0-1"| S1["(0011, 1)"]
S1 -->|"1-0"| S2["(0011, 0)"]
S2 -->|"0-2"| S3["(0111, 2)"]
S3 -->|"2-0"| S4["(0111, 0)"]
S4 -->|"0-3"| S5["(1111, 3) : full"]
For the star graph with centre 0 and leaves 1, 2, 3 ([[1,2,3],[0],[0],[0]]), one optimal walk is , length 4. The diagram shows a different but less efficient walk starting at 0 (length 5); BFS, starting from all nodes at once, finds the length-4 walk starting at a leaf.
from collections import deque
def shortest_path_length(graph):
n = len(graph)
full = (1 << n) - 1
dist = [[-1] * n for _ in range(1 << n)]
q = deque()
for v in range(n):
dist[1 << v][v] = 0
q.append((1 << v, v))
while q:
mask, v = q.popleft()
d = dist[mask][v]
if mask == full:
return d
for w in graph[v]:
nxt = mask | (1 << w)
if dist[nxt][w] < 0:
dist[nxt][w] = d + 1
q.append((nxt, w))
return -1
assert shortest_path_length([[1, 2, 3], [0], [0], [0]]) == 4
assert shortest_path_length([[1], [0, 2, 4], [1, 3, 4], [2], [1, 2]]) == 4
assert shortest_path_length([[]]) == 0
states, each with edges: in total, about operations at most for LeetCode's limits.
Weighted version. If edges have weights, run Dijkstra on the same state graph, or first compute all-pairs shortest distances (Floyd–Warshall, see Shortest Paths) and then run Held–Karp on the resulting complete graph — "visit all, revisits allowed" on a graph equals "visit each once" on its metric closure.
7. Iterating submasks, and why it costs
Some transitions add a whole group at once: "split the items into groups; a group's score depends on all its members". Then dp[mask] = best way to partition mask into groups, and
You need to loop over all submasks of mask (masks whose 1-bits are a subset of mask's 1-bits). The standard idiom:
def submasks(mask):
s = mask
while s > 0:
yield s
s = (s - 1) & mask # next smaller submask
assert [format(s, "04b") for s in submasks(0b1011)] == ["1011", "1010", "1001", "1000", "0011", "0010", "0001"]
Why (s - 1) & mask works. Subtracting 1 flips the lowest 1-bit of to 0 and all bits below it to 1. ANDing with mask keeps only the bits that are allowed. The result is the largest submask of mask smaller than . Treat the allowed bit positions as a smaller binary number: you are simply counting down in that number. So the loop visits every non-empty submask exactly once, in decreasing order. (Add the empty set separately if you need it.)
Why the total over all masks is , not . The loop
for mask in 0 .. 2^n - 1:
for s in submasks(mask): ...
runs once per pair with . For each item there are exactly three options: in neither, in mask but not s, or in both. Items are independent, so there are pairs. Equivalently, by the binomial theorem. For , — fine. For , — too slow in most judges. Compare for the naive "all pairs of masks, test (s & mask) == s".
A common refinement: to avoid counting the same partition many times in different group orders, force the group to contain the lowest set bit of mask. The answer is unchanged and the work drops (the groups are now generated in a canonical order).
Here is the work-sessions problem again with submask transitions, as a cross-check:
def min_sessions_submask(tasks, T):
n = len(tasks)
total = [0] * (1 << n)
for mask in range(1, 1 << n):
low = (mask & -mask).bit_length() - 1
total[mask] = total[mask & (mask - 1)] + tasks[low] # sum of tasks in mask
INF = n + 1
dp = [INF] * (1 << n)
dp[0] = 0
for mask in range(1, 1 << n):
low_bit = mask & -mask
s = mask
while s > 0:
if s & low_bit and total[s] <= T: # s is one session
dp[mask] = min(dp[mask], dp[mask ^ s] + 1)
s = (s - 1) & mask
return dp[(1 << n) - 1]
assert min_sessions_submask([1, 2, 3], 3) == 2
assert min_sessions_submask([3, 1, 3, 1, 1], 8) == 2
assert min_sessions_submask([1, 2, 3, 4, 5], 15) == 1
It is instead of : slower, but it needs no dominance argument, so it is the safer first idea when the group score is complicated. When the inner work is a sum or max over all submasks with no "pick one group" structure, SOS DP brings down to .
Feasibility limits and memory math
Bitmask DP is exponential. Before writing code, multiply out the state count and the bytes. The numbers below are exact.
| TSP states | TSP transitions | TSP table, 4-byte ints | TSP table, 8-byte ints | Assignment table , 4-byte | ||
|---|---|---|---|---|---|---|
| 10 | 1,024 | 10,240 | 102,400 | 40 KiB | 80 KiB | 4 KiB |
| 15 | 32,768 | 491,520 | 7,372,800 | 1.9 MiB | 3.8 MiB | 128 KiB |
| 16 | 65,536 | 1,048,576 | 16,777,216 | 4 MiB | 8 MiB | 256 KiB |
| 18 | 262,144 | 4,718,592 | 84,934,656 | 18 MiB | 36 MiB | 1 MiB |
| 20 | 1,048,576 | 20,971,520 | 419,430,400 | 80 MiB | 160 MiB | 4 MiB |
| 22 | 4,194,304 | 92,274,688 | 2,030,043,136 | 352 MiB | 704 MiB | 16 MiB |
| 24 | 16,777,216 | 402,653,184 | 9,663,676,416 | 1.5 GiB | 3 GiB | 64 MiB |
Rules of thumb for a judge that runs about – simple operations per second with a 256 MiB limit:
dp[mask][v]with an transition: is comfortable everywhere (including Python), is fine in C++/Java with 32-bit values, – needs tricks.dp[mask]with an transition (assignment): in C++/Java; Python up to about 18–20.- Submask enumeration : comfortable, () borderline in C++.
- A parent table doubles the memory. For , TSP with 4-byte costs and 1-byte parents is MiB.
Tricks that buy a factor of 2 or more:
- Drop the fixed start from the mask. In TSP every reachable mask contains city 0, so index masks over cities only: states, less than half.
- Use the smallest type that holds the answer. Distances up to over 20 legs fit in 32 bits; counts modulo fit in 32 bits unsigned (add in 64 bits, then reduce).
- Recompute parents instead of storing them. Walking back, the previous city is any one with
dp[mask \ {j}][p] + dist[p][j] == dp[mask][j]. That is per step, total, and saves the whole parent table. - Lay memory out as
dp[mask][v](mask outer) so the inner loop overvtouches consecutive memory.dp[v][mask]scatters writes across 20 arrays. - Skip dead states early (
if dp[mask][j] == INF: continue) — in sparse graphs most states are unreachable.
Python and
A list of lists of 20 Python ints holds about 21 million object references: roughly 170 MiB for the references alone, and the -step loop would take many minutes. In Python, keep – for dp[mask][v], or switch to NumPy/array-based layouts, or use C++/Java.
The ladder: brute force → better → optimal
Problem: exact TSP on cities.
Rung 1: try every order
Fix city 0 as the start (a tour is a cycle, so its starting point does not matter) and try all orders of the rest. Each costs to evaluate.
from itertools import permutations
def tsp_brute(dist):
n = len(dist)
best = None
for order in permutations(range(1, n)):
route = (0,) + order + (0,)
cost = sum(dist[a][b] for a, b in zip(route, route[1:]))
best = cost if best is None else min(best, cost)
return best if n > 1 else 0
assert tsp_brute([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]) == 80
. is about 4 million orders — fine. is — not fine. Its value: an obviously correct oracle to test the DP against.
Rung 2: backtracking with pruning (branch and bound)
Extend the route city by city; abandon a branch as soon as its cost already exceeds the best complete tour found. With a good lower bound (for example, the current cost plus a minimum spanning tree of the unvisited cities) this solves many instances of 20–30 cities quickly, but the worst case is still . See Backtracking & Recursion.
Rung 3: memoised recursion over (set, city)
Notice that the backtracking keeps re-solving "finish the tour from city with set left". Memoise on : there are only such questions. This is Held–Karp, top-down. Each question looks at next cities: .
Rung 4: tabulated Held–Karp
The same recurrence filled in increasing mask order, with no recursion overhead, plus a parent table for the tour. This is the version in Implementation.
Beyond: heuristics and exact solvers for big
For hundreds or thousands of cities nobody uses DP. Exact solvers such as Concorde use linear-programming relaxations with cutting planes inside branch and bound (Applegate, Bixby, Chvátal, Cook), and solved an 85,900-city instance (pla85900) to optimality. Heuristics such as 2-opt and Lin–Kernighan (LKH) find tours within a fraction of a percent of optimal in seconds. See Heuristics & Metaheuristics.
| Rung | Method | Time | Space | Why it is better than the rung above |
|---|---|---|---|---|
| 1 | All orders | Baseline; obviously correct | ||
| 2 | Branch and bound | worst, often much less | Cuts hopeless branches early; no guarantee | |
| 3 | Memoised (set, city) | + recursion | Each (set, city) question solved once instead of once per order | |
| 4 | Tabulated Held–Karp | No recursion; easy parent table; cache-friendly | ||
| beyond | LP + cuts / LKH | no useful worst-case bound | polynomial | Solves thousands of cities in practice; exponential-free in typical cases |
To feel the gap: at , rung 1 needs orders and rung 4 needs steps — about 80,000 times less work.
Correctness
Held–Karp. Claim: after all masks smaller than mask have been processed, dp[mask][j] equals the minimum cost of a path from 0 that visits exactly mask and ends at . Induction on .
- Base: with : the empty path, cost 0. Every other state with one city is unreachable (infinite), correctly, since paths start at 0.
- Step: take an optimal path for
(mask, j), . Let be the city just before . Removing gives a path from 0 that visits exactly and ends at . must be an optimal such path: if a cheaper existed, followed by would be a cheaper path for(mask, j)— still valid, because avoids . (This is the cut-and-paste argument of CLRS §14.3.) By inductiondp[mask \ {j}][p]equals the cost of , and the push from that state offereddp[mask][j]exactly the cost of . Conversely every value the DP writes is the cost of a real path. So the minimum is exact. - Order: every push goes from a smaller integer to a larger one, so all pushes into
maskhappen beforemaskis read. - Answer: every tour is a Hamiltonian path from 0 to some plus the edge ; minimising over covers all tours.
Reconstruction. parent[mask][j] records the that gave the final (minimum) value. Following parents produces a path whose cost telescopes to dp[full][j], and the masks shrink by exactly one city per step, so the walk visits every city once and stops at the base state.
Assignment. There is a bijection between "assignments of jobs to workers " and "orders in which the jobs in a -bit mask were handed out". Two partial assignments with the same job set give the remaining workers exactly the same options, so only the cheaper one matters — the same exchange argument as above. Induction on popcount gives dp[mask] correct.
Partition into subsets. Invariant: load[mask] iff the elements of mask can be listed in an order such that, cutting the list into consecutive pieces of sum target plus one shorter last piece, no piece exceeds target. Any valid partition gives such a list (list the groups one after another), and such a list for the full set gives a valid partition. The load value is forced (), so a boolean is enough.
BFS over states. The state graph has unit edge weights; BFS from a set of sources visits states in non-decreasing distance (the standard BFS invariant, proven in BFS in Depth). A walk in the original graph that visits every node corresponds to a path in the state graph from some ({v}, v) to some (full, w), and vice versa, with the same length.
Complexity
| Problem | States | Transitions per state | Time | Memory |
|---|---|---|---|---|
| TSP (Held–Karp) | ||||
| Assignment | ||||
| Hamiltonian path count | , | |||
| Partition into | ||||
| Work sessions (pair state) | ||||
| Work sessions (submasks) | up to | |||
| BFS over (node, mask) |
Best, average and worst case coincide for the table-filling versions: every state is visited. Skipping unreachable states helps on sparse inputs but not in the worst case. Bitmask DP is not amortised in any interesting way; its cost is simply the size of the state space times the work per state.
Lower bounds are open questions. For TSP with arbitrary weights, (the hides polynomial factors) has not been beaten since 1962. Under the Strong Exponential Time Hypothesis, many set problems are believed to need time, but no such proof exists for TSP.
Implementation
Held–Karp with tour reconstruction and the assignment DP with reconstruction, in four languages. Each program checks the two examples from this lesson and then compares both DPs against brute force over all permutations on 200 random instances with up to 7 cities/workers.
import random
from itertools import permutations
from typing import List, Tuple
INF = 10**18
def held_karp(dist: List[List[int]]) -> Tuple[int, List[int]]:
"""Cheapest tour 0 -> ... -> 0 visiting every city once. Returns (cost, tour)."""
n = len(dist)
if n == 1:
return 0, [0, 0]
full = (1 << n) - 1
dp = [[INF] * n for _ in range(1 << n)]
parent = [[-1] * n for _ in range(1 << n)]
dp[1][0] = 0 # visited {0}, standing at 0
for mask in range(1, 1 << n):
if not mask & 1: # every path starts at city 0
continue
row = dp[mask]
for j in range(n):
cur = row[j]
if cur == INF:
continue
for k in range(n):
if (mask >> k) & 1:
continue
nxt = mask | (1 << k)
cand = cur + dist[j][k]
if cand < dp[nxt][k]:
dp[nxt][k] = cand
parent[nxt][k] = j
best, last = min((dp[full][j] + dist[j][0], j) for j in range(1, n))
tour, mask, j = [], full, last
while j != -1: # walk the parent pointers back to city 0
tour.append(j)
prev = parent[mask][j]
mask ^= 1 << j
j = prev
tour.reverse()
tour.append(0)
return best, tour
def min_cost_assignment(cost: List[List[int]]) -> Tuple[int, List[int]]:
"""Worker i (row) gets job_of[i] (column); minimise the total cost."""
n = len(cost)
dp = [INF] * (1 << n)
last_job = [-1] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
if dp[mask] == INF:
continue
i = bin(mask).count("1") # next worker = number of jobs used
if i == n:
continue
for j in range(n):
if not (mask >> j) & 1:
nxt = mask | (1 << j)
cand = dp[mask] + cost[i][j]
if cand < dp[nxt]:
dp[nxt] = cand
last_job[nxt] = j
job_of = [0] * n
mask = (1 << n) - 1
for i in range(n - 1, -1, -1): # the last job added belongs to worker i
job_of[i] = last_job[mask]
mask ^= 1 << job_of[i]
return dp[(1 << n) - 1], job_of
def tour_cost(dist, tour):
return sum(dist[a][b] for a, b in zip(tour, tour[1:]))
def main() -> None:
dist = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
assert held_karp(dist) == (80, [0, 2, 3, 1, 0])
cost = [[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 9, 4]]
assert min_cost_assignment(cost) == (13, [1, 0, 2, 3])
rng = random.Random(1)
for _ in range(200):
n = rng.randint(1, 7)
d = [[0 if i == j else rng.randint(1, 50) for j in range(n)] for i in range(n)] # asymmetric
best, tour = held_karp(d)
brute = min((tour_cost(d, (0,) + p + (0,)) for p in permutations(range(1, n))), default=0)
assert best == brute == tour_cost(d, tour)
assert sorted(tour[:-1]) == list(range(n)) and tour[0] == tour[-1] == 0
c = [[rng.randint(0, 30) for _ in range(n)] for _ in range(n)]
total, job_of = min_cost_assignment(c)
assert sorted(job_of) == list(range(n))
assert total == sum(c[i][job_of[i]] for i in range(n))
assert total == min(sum(c[i][p[i]] for i in range(n)) for p in permutations(range(n)))
print("tour:", held_karp(dist), "assignment:", min_cost_assignment(cost))
if __name__ == "__main__":
main()
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
public class BitmaskDp {
static final long INF = Long.MAX_VALUE / 4;
/** Returns the tour as a list starting and ending at 0; the cost is put in costOut[0]. */
static List<Integer> heldKarp(long[][] dist, long[] costOut) {
int n = dist.length;
if (n == 1) { costOut[0] = 0; return List.of(0, 0); }
int full = (1 << n) - 1;
long[][] dp = new long[1 << n][n];
int[][] parent = new int[1 << n][n];
for (long[] row : dp) Arrays.fill(row, INF);
for (int[] row : parent) Arrays.fill(row, -1);
dp[1][0] = 0;
for (int mask = 1; mask <= full; mask++) {
if ((mask & 1) == 0) continue;
for (int j = 0; j < n; j++) {
long cur = dp[mask][j];
if (cur == INF) continue;
for (int k = 0; k < n; k++) {
if (((mask >> k) & 1) != 0) continue;
int nxt = mask | (1 << k);
long cand = cur + dist[j][k];
if (cand < dp[nxt][k]) { dp[nxt][k] = cand; parent[nxt][k] = j; }
}
}
}
long best = INF;
int last = -1;
for (int j = 1; j < n; j++) {
long c = dp[full][j] + dist[j][0];
if (c < best) { best = c; last = j; }
}
List<Integer> tour = new ArrayList<>();
int mask = full, j = last;
while (j != -1) {
tour.add(j);
int prev = parent[mask][j];
mask ^= 1 << j;
j = prev;
}
Collections.reverse(tour);
tour.add(0);
costOut[0] = best;
return tour;
}
/** Returns jobOf[i] for each worker i; the total cost is put in costOut[0]. */
static int[] minCostAssignment(long[][] cost, long[] costOut) {
int n = cost.length;
long[] dp = new long[1 << n];
int[] lastJob = new int[1 << n];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] == INF) continue;
int i = Integer.bitCount(mask);
if (i == n) continue;
for (int j = 0; j < n; j++) {
if (((mask >> j) & 1) != 0) continue;
int nxt = mask | (1 << j);
long cand = dp[mask] + cost[i][j];
if (cand < dp[nxt]) { dp[nxt] = cand; lastJob[nxt] = j; }
}
}
int[] jobOf = new int[n];
int mask = (1 << n) - 1;
for (int i = n - 1; i >= 0; i--) { jobOf[i] = lastJob[mask]; mask ^= 1 << jobOf[i]; }
costOut[0] = dp[(1 << n) - 1];
return jobOf;
}
static long tourCost(long[][] d, List<Integer> t) {
long s = 0;
for (int i = 0; i + 1 < t.size(); i++) s += d[t.get(i)][t.get(i + 1)];
return s;
}
// Brute force over permutations of a[from..]: minimum of f over all orders.
interface Eval { long apply(int[] perm); }
static long bestPerm(int[] a, int from, Eval f) {
if (from == a.length) return f.apply(a);
long best = INF;
for (int i = from; i < a.length; i++) {
int t = a[from]; a[from] = a[i]; a[i] = t;
best = Math.min(best, bestPerm(a, from + 1, f));
t = a[from]; a[from] = a[i]; a[i] = t;
}
return best;
}
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) {
long[][] dist = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};
long[] out = new long[1];
List<Integer> tour = heldKarp(dist, out);
check(out[0] == 80 && tour.equals(List.of(0, 2, 3, 1, 0)), "tsp example");
long[][] cost = {{9, 2, 7, 8}, {6, 4, 3, 7}, {5, 8, 1, 8}, {7, 6, 9, 4}};
int[] jobOf = minCostAssignment(cost, out);
check(out[0] == 13 && Arrays.equals(jobOf, new int[]{1, 0, 2, 3}), "assignment example");
Random rng = new Random(1);
for (int iter = 0; iter < 200; iter++) {
int n = 1 + rng.nextInt(7);
long[][] d = new long[n][n];
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = i == j ? 0 : 1 + rng.nextInt(50);
List<Integer> t = heldKarp(d, out);
long dpCost = out[0];
int[] rest = new int[n]; // rest[0] = 0 stays fixed; permute rest[1..]
for (int i = 0; i < n; i++) rest[i] = i;
long brute = n == 1 ? 0 : bestPerm(rest, 1, p -> {
long s = 0;
for (int i = 0; i < n; i++) s += d[p[i]][p[(i + 1) % n]];
return s;
});
check(dpCost == brute && tourCost(d, t) == dpCost, "tsp random");
long[][] c = new long[n][n];
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) c[i][j] = rng.nextInt(31);
int[] jo = minCostAssignment(c, out);
long total = 0;
for (int i = 0; i < n; i++) total += c[i][jo[i]];
int[] ids = new int[n];
for (int i = 0; i < n; i++) ids[i] = i;
long bruteA = bestPerm(ids, 0, p -> {
long s = 0;
for (int i = 0; i < n; i++) s += c[i][p[i]];
return s;
});
check(total == out[0] && total == bruteA, "assignment random");
}
System.out.println("tour: 80 " + tour + " assignment: 13 " + Arrays.toString(jobOf));
}
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <random>
#include <utility>
#include <vector>
using namespace std;
const int64_t INF = INT64_MAX / 4;
// Returns {cost, tour}; the tour starts and ends at city 0.
pair<int64_t, vector<int>> heldKarp(const vector<vector<int64_t>>& dist) {
int n = dist.size();
if (n == 1) return {0, {0, 0}};
int full = (1 << n) - 1;
vector<vector<int64_t>> dp(1 << n, vector<int64_t>(n, INF));
vector<vector<int>> parent(1 << n, vector<int>(n, -1));
dp[1][0] = 0;
for (int mask = 1; mask <= full; ++mask) {
if (!(mask & 1)) continue;
for (int j = 0; j < n; ++j) {
int64_t cur = dp[mask][j];
if (cur == INF) continue;
for (int k = 0; k < n; ++k) {
if ((mask >> k) & 1) continue;
int nxt = mask | (1 << k);
int64_t cand = cur + dist[j][k];
if (cand < dp[nxt][k]) { dp[nxt][k] = cand; parent[nxt][k] = j; }
}
}
}
int64_t best = INF;
int last = -1;
for (int j = 1; j < n; ++j)
if (dp[full][j] + dist[j][0] < best) { best = dp[full][j] + dist[j][0]; last = j; }
vector<int> tour;
for (int mask = full, j = last; j != -1;) {
tour.push_back(j);
int prev = parent[mask][j];
mask ^= 1 << j;
j = prev;
}
reverse(tour.begin(), tour.end());
tour.push_back(0);
return {best, tour};
}
// Returns {cost, jobOf}: worker i does job jobOf[i].
pair<int64_t, vector<int>> minCostAssignment(const vector<vector<int64_t>>& cost) {
int n = cost.size();
vector<int64_t> dp(1 << n, INF);
vector<int> lastJob(1 << n, -1);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); ++mask) {
if (dp[mask] == INF) continue;
int i = __builtin_popcount(mask);
if (i == n) continue;
for (int j = 0; j < n; ++j) {
if ((mask >> j) & 1) continue;
int nxt = mask | (1 << j);
if (dp[mask] + cost[i][j] < dp[nxt]) { dp[nxt] = dp[mask] + cost[i][j]; lastJob[nxt] = j; }
}
}
vector<int> jobOf(n);
int mask = (1 << n) - 1;
for (int i = n - 1; i >= 0; --i) { jobOf[i] = lastJob[mask]; mask ^= 1 << jobOf[i]; }
return {dp[(1 << n) - 1], jobOf};
}
int main() {
vector<vector<int64_t>> dist = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};
auto [tc, tour] = heldKarp(dist);
assert(tc == 80 && (tour == vector<int>{0, 2, 3, 1, 0}));
vector<vector<int64_t>> cost = {{9, 2, 7, 8}, {6, 4, 3, 7}, {5, 8, 1, 8}, {7, 6, 9, 4}};
auto [ac, jobOf] = minCostAssignment(cost);
assert(ac == 13 && (jobOf == vector<int>{1, 0, 2, 3}));
mt19937 rng(1);
for (int iter = 0; iter < 200; ++iter) {
int n = 1 + rng() % 7;
vector<vector<int64_t>> d(n, vector<int64_t>(n)), c(n, vector<int64_t>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) { d[i][j] = i == j ? 0 : 1 + rng() % 50; c[i][j] = rng() % 31; }
auto [best, t] = heldKarp(d);
vector<int> p(n);
iota(p.begin(), p.end(), 0);
int64_t brute = n == 1 ? 0 : INF;
if (n > 1) do { // p[0] = 0 stays first
int64_t s = 0;
for (int i = 0; i < n; ++i) s += d[p[i]][p[(i + 1) % n]];
brute = min(brute, s);
} while (next_permutation(p.begin() + 1, p.end()));
int64_t walked = 0;
for (size_t i = 0; i + 1 < t.size(); ++i) walked += d[t[i]][t[i + 1]];
assert(best == brute && walked == best);
auto [total, jo] = minCostAssignment(c);
iota(p.begin(), p.end(), 0);
int64_t bruteA = INF;
do {
int64_t s = 0;
for (int i = 0; i < n; ++i) s += c[i][p[i]];
bruteA = min(bruteA, s);
} while (next_permutation(p.begin(), p.end()));
int64_t check = 0;
for (int i = 0; i < n; ++i) check += c[i][jo[i]];
assert(total == bruteA && check == total);
}
cout << "tour cost " << tc << ", assignment cost " << ac << "\n";
}
const INF = Number.MAX_SAFE_INTEGER;
function popcount(x: number): number {
let c = 0;
while (x) { x &= x - 1; c++; }
return c;
}
function heldKarp(dist: number[][]): [number, number[]] {
const n = dist.length;
if (n === 1) return [0, [0, 0]];
const full = (1 << n) - 1;
const dp: Float64Array[] = Array.from({ length: 1 << n }, () => new Float64Array(n).fill(INF));
const parent: Int8Array[] = Array.from({ length: 1 << n }, () => new Int8Array(n).fill(-1));
dp[1][0] = 0;
for (let mask = 1; mask <= full; mask++) {
if (!(mask & 1)) continue;
for (let j = 0; j < n; j++) {
const cur = dp[mask][j];
if (cur === INF) continue;
for (let k = 0; k < n; k++) {
if ((mask >> k) & 1) continue;
const nxt = mask | (1 << k);
const cand = cur + dist[j][k];
if (cand < dp[nxt][k]) { dp[nxt][k] = cand; parent[nxt][k] = j; }
}
}
}
let best = INF, last = -1;
for (let j = 1; j < n; j++) {
const c = dp[full][j] + dist[j][0];
if (c < best) { best = c; last = j; }
}
const tour: number[] = [];
for (let mask = full, j = last; j !== -1;) {
tour.push(j);
const prev = parent[mask][j];
mask ^= 1 << j;
j = prev;
}
tour.reverse();
tour.push(0);
return [best, tour];
}
function minCostAssignment(cost: number[][]): [number, number[]] {
const n = cost.length;
const dp = new Float64Array(1 << n).fill(INF);
const lastJob = new Int8Array(1 << n).fill(-1);
dp[0] = 0;
for (let mask = 0; mask < (1 << n); mask++) {
if (dp[mask] === INF) continue;
const i = popcount(mask);
if (i === n) continue;
for (let j = 0; j < n; j++) {
if ((mask >> j) & 1) continue;
const nxt = mask | (1 << j);
const cand = dp[mask] + cost[i][j];
if (cand < dp[nxt]) { dp[nxt] = cand; lastJob[nxt] = j; }
}
}
const jobOf: number[] = new Array(n).fill(0);
let mask = (1 << n) - 1;
for (let i = n - 1; i >= 0; i--) { jobOf[i] = lastJob[mask]; mask ^= 1 << jobOf[i]; }
return [dp[(1 << n) - 1], jobOf];
}
function* perms(a: number[]): Generator<number[]> {
if (a.length <= 1) { yield a.slice(); return; }
for (let i = 0; i < a.length; i++) {
const rest = a.slice(0, i).concat(a.slice(i + 1));
for (const p of perms(rest)) yield [a[i], ...p];
}
}
function assert(ok: boolean, msg: string): void {
if (!ok) throw new Error(msg);
}
// Small deterministic PRNG (mulberry32) so runs are reproducible.
function rng(seed: number): () => number {
return () => {
seed = (seed + 0x6d2b79f5) | 0;
let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
const dist = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]];
const [tc, tour] = heldKarp(dist);
assert(tc === 80 && tour.join() === "0,2,3,1,0", "tsp example");
const cost = [[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 9, 4]];
const [ac, jobOf] = minCostAssignment(cost);
assert(ac === 13 && jobOf.join() === "1,0,2,3", "assignment example");
const rand = rng(1);
const randInt = (lo: number, hi: number) => lo + Math.floor(rand() * (hi - lo + 1));
for (let iter = 0; iter < 200; iter++) {
const n = randInt(1, 7);
const d = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : randInt(1, 50))));
const [best, t] = heldKarp(d);
let brute = n === 1 ? 0 : INF;
if (n > 1) {
for (const p of perms(Array.from({ length: n - 1 }, (_, i) => i + 1))) {
const route = [0, ...p, 0];
let s = 0;
for (let i = 0; i + 1 < route.length; i++) s += d[route[i]][route[i + 1]];
brute = Math.min(brute, s);
}
}
let walked = 0;
for (let i = 0; i + 1 < t.length; i++) walked += d[t[i]][t[i + 1]];
assert(best === brute && walked === best, "tsp random");
const c = Array.from({ length: n }, () => Array.from({ length: n }, () => randInt(0, 30)));
const [total, jo] = minCostAssignment(c);
let bruteA = INF;
for (const p of perms(Array.from({ length: n }, (_, i) => i))) {
bruteA = Math.min(bruteA, p.reduce((s, job, i) => s + c[i][job], 0));
}
assert(total === bruteA && jo.reduce((s, job, i) => s + c[i][job], 0) === total, "assignment random");
}
console.log("tour", tc, tour, "assignment", ac, jobOf);
Notes on the choices. Java and C++ use 64-bit costs with INF = MAX / 4 so that INF + dist cannot overflow even though the code skips INF states anyway. TypeScript uses Float64Array (exact for integers below ) and Int8Array parents (city indices fit in a byte for ). All four use dp[mask][j] with the mask outermost for locality. None of them drops city 0 from the mask; that halving trick is left as an exercise in the practice ladder.
Real-world uses
- Join ordering in SQL query optimisers. Choosing the order in which to join tables is a set problem: the best plan for joining a set of tables does not depend on how that set was assembled. IBM's System R optimiser (Selinger et al., "Access Path Selection in a Relational Database Management System", SIGMOD 1979) introduced dynamic programming over subsets of relations, and it remains the core of most optimisers. PostgreSQL's standard planner builds join relations level by level, keyed by the set of base relations they cover, and switches to its genetic optimiser GEQO once a query reaches
geqo_threshold(default 12) relations — exactly because the subset DP explodes. Moerkotte and Neumann's DPccp algorithm (VLDB 2006) enumerates only connected subsets to make the DP faster. See Query Planning & Optimization. - Steiner trees in VLSI routing and network design. The Dreyfus–Wagner algorithm (1971) connects terminal nodes in a graph at minimum cost with a DP over subsets of terminals, time (with Floyd–Warshall for the last term); it is used exactly when (pins of a net) is small.
- Small exact routing. Pick-paths in a warehouse for one order of 10–15 items, the visiting order of a robot or drone over a handful of waypoints, and ordering drill holes in a small batch are TSP instances small enough for Held–Karp; larger ones go to heuristics (Lin–Kernighan, LKH) or Concorde. Routing libraries such as Google OR-Tools solve these with constraint programming and local search rather than DP; Held–Karp is the go-to when the instance is tiny and you need a proof of optimality in a few milliseconds.
- Bioinformatics. Shortest common superstring of a few reads (genome fragment assembly in its simplest model) reduces to an asymmetric TSP on overlap lengths — LeetCode 943 is this exact problem.
- Scheduling with setup times. Ordering jobs on one machine when switching from job to job costs is the asymmetric TSP — the original motivation of Held and Karp's "sequencing problems" paper.
Pitfalls & edge cases
n = 1. The answer loopmin over j in 1..n-1is empty. Handle it (tour cost 0).- Masks without the start. In TSP, masks not containing city 0 are unreachable; either skip them or drop city 0 from the mask altogether. Forgetting this does not break correctness but wastes half the time.
- Operator precedence in C-like languages:
mask & 1 << k == 0is wrong. Parenthesise. 1 << noverflows for in 32-bitint(and Java1 << 32 == 1). Bitmask DP never needs , but1L << k/1ULL << kis needed when you use 64-bit masks for other reasons.- INF overflow.
INF + dist[j][k]withINF = INT_MAXwraps to a negative number and becomes the "best". UseINF = MAX / 4or skip INF states. - Wrong iteration order with pull-style transitions. If you write
dp[mask][j] = min over p of dp[mask ^ (1<<j)][p] + …, increasing mask order is still correct (the source mask is smaller). But in the BFS problem (revisits allowed) there is no such order — use BFS. - Confusing "visit each exactly once" with "visit all, revisits allowed". The first is Held–Karp/Hamiltonian; the second is BFS/Dijkstra over
(node, mask)or Held–Karp on all-pairs shortest distances. - Assignment with workers and jobs. The worker index is still the popcount; the mask ranges over the jobs and the answer is the minimum over all masks with popcount . The table has entries, so if is the large side, swap roles where the problem allows it (LeetCode 1434 puts the 10 people in the mask, not the 40 hats).
- Counting modulo . Reduce after each addition; with 32-bit storage add in 64 bits.
- Python speed. TSP is 16.7 million inner steps: about 5–10 seconds in CPython. Prune INF states, precompute bit lists, or use PyPy.
Variations
- Drop the fixed start. Index the mask over cities ; halves memory and time.
- Path instead of cycle. For "shortest Hamiltonian path with free endpoints", start from all
({v}, v)with cost 0 and take with no return edge. - Profile / broken-profile DP. When the "set" is the occupied cells along a grid frontier: Broken-Profile DP.
- Sum over subsets. When every mask needs an aggregate over all its submasks: SOS DP.
- Meet in the middle. For subset-sum-like problems with , split into two halves of 20, enumerate sums each, and combine by sorting or hashing.
- Inclusion–exclusion for Hamiltonian cycles. Counting Hamiltonian cycles via inclusion–exclusion over the missing vertex sets uses polynomial memory and time (Karp 1982; Bax 1993) — useful when memory is too much.
- Faster Hamiltonicity. Björklund's randomised algorithm ("Determinant sums for undirected Hamiltonicity", FOCS 2010) decides Hamiltonicity of undirected graphs in . It does not apply to weighted TSP.
- Steiner tree DP.
dp[S][v]= cheapest tree connecting terminal set and vertex ; merges submasks () and then relaxes with Dijkstra. - Bitset speed-ups. Store, for each mask, a bitmask of reachable end vertices; transitions become ANDs/ORs of adjacency masks.
- Bitonic TSP. If the tour must go left-to-right then right-to-left (points sorted by ), an DP exists (CLRS problem 14-3); no bitmask needed.
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Beautiful Arrangement (LeetCode 526) — Count permutations of () where every position and the number in it divide one another in one direction or the other. Teaches dp[mask] with the position given by popcount, counting version.
Hint
Position . dp[mask | bit(x)] += dp[mask] when and divide one another.
2. Shortest Path Visiting All Nodes (LeetCode 847) — Shortest walk in a small graph that touches every node. Teaches BFS over (node, mask).
Hint
The code in §6 is a full solution. Multi-source start: every ({v}, v) at distance 0.
3. Partition to K Equal Sum Subsets (LeetCode 698) — Split up to 16 numbers into groups of equal sum. Teaches "the load is a function of the mask".
Hint
§4 is a full solution. The only state is the mask; the open bucket's load is sum(mask) % target.
4. Minimum Number of Work Sessions to Finish the Tasks (LeetCode 1986) — Pack up to 14 tasks into the fewest sessions of bounded length. Teaches the (count, load) pair state and its dominance argument.
Hint
§5 gives both the pair-state and the submask solutions.
5. Elevator Rides (CSES 1653) — The same as #4 with people and a weight limit. Teaches that only the pair state survives ( is too slow).
Hint
Same code as min_sessions, in C++ or Java with two arrays (rides, last load) of size .
6. Minimum XOR Sum of Two Arrays (LeetCode 1879) — Pair up two arrays of length to minimise the sum of XORs of pairs. Teaches that the assignment DP handles any pairwise cost.
Solution
Element of nums1 is the "worker" (popcount), elements of nums2 are the "jobs". .
def minimum_xor_sum(nums1, nums2):
n = len(nums1)
INF = float("inf")
dp = [INF] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
i = bin(mask).count("1")
if i == n or dp[mask] == INF:
continue
for j in range(n):
if not (mask >> j) & 1:
nxt = mask | (1 << j)
dp[nxt] = min(dp[nxt], dp[mask] + (nums1[i] ^ nums2[j]))
return dp[(1 << n) - 1]
assert minimum_xor_sum([1, 2], [2, 3]) == 2
assert minimum_xor_sum([1, 0, 3], [5, 3, 4]) == 8
7. Matching (AtCoder Educational DP Contest, problem O) — Count the perfect matchings between men and women given a compatibility matrix, modulo . Teaches the counting version of the assignment DP — something the Hungarian algorithm cannot do.
Solution
Replace min with +. masks × 21 = steps: fine in C++, slow in Python (use the push form and skip zero states).
def count_perfect_matchings(compat, mod=10**9 + 7):
n = len(compat)
dp = [0] * (1 << n)
dp[0] = 1
for mask in range(1 << n):
ways = dp[mask]
if ways == 0:
continue
i = bin(mask).count("1") # next man
if i == n:
continue
for j in range(n):
if compat[i][j] and not (mask >> j) & 1:
nxt = mask | (1 << j)
dp[nxt] = (dp[nxt] + ways) % mod
return dp[(1 << n) - 1]
assert count_perfect_matchings([[0, 1, 1], [1, 0, 1], [1, 1, 1]]) == 3
assert count_perfect_matchings([[1] * 4 for _ in range(4)]) == 24 # all 4! permutations
8. Hamiltonian Flights (CSES 1690) — Count flight routes from city 1 to city () visiting every city exactly once, modulo ; there can be several flights between two cities. Teaches the Hamiltonian counting DP and the "goal reached too early" pruning.
Solution
count_hamiltonian_paths from §3 with mod = 10**9 + 7, translated to C++ (Python is too slow for ). Pull-style transitions over incoming edges are cache-friendlier: ways[mask][v] = sum over edges u -> v of ways[mask ^ bit(v)][u].
9. Smallest Sufficient Team (LeetCode 1125) — Choose the fewest people whose skills (at most 16 skills in total) cover all required skills. Teaches a bitmask over requirements rather than over items: dp[skillMask] = smallest team covering it.
Hint
Turn each person into a skill mask. dp[mask | person] = min(dp[mask] + 1), remembering which person and which previous mask to rebuild the team. The mask is over 16 skills; the people (up to 60) are just transitions.
10. Grouping (AtCoder Educational DP Contest, problem U) — Split rabbits into groups to maximise the total of pairwise compatibility scores inside groups. Teaches submask enumeration in .
Solution
Precompute score[mask] (sum of pair scores inside mask) incrementally, then dp[mask] = max over submask s containing the lowest bit of mask of score[s] + dp[mask ^ s].
def grouping(a):
n = len(a)
score = [0] * (1 << n)
for mask in range(1, 1 << n):
low = (mask & -mask).bit_length() - 1
rest = mask & (mask - 1)
score[mask] = score[rest] + sum(a[low][j] for j in range(n) if (rest >> j) & 1)
dp = [0] * (1 << n)
for mask in range(1, 1 << n):
low_bit = mask & -mask
best = None
s = mask
while s > 0:
if s & low_bit:
cand = score[s] + dp[mask ^ s]
best = cand if best is None else max(best, cand)
s = (s - 1) & mask
dp[mask] = best
return dp[(1 << n) - 1]
assert grouping([[0, 10, 20], [10, 0, -100], [20, -100, 0]]) == 20
assert grouping([[0, -10], [-10, 0]]) == 0
11. A Simple Task (Codeforces 11D) — Count the simple cycles in an undirected graph with vertices. Teaches canonical forms: count each cycle from its smallest vertex and divide by 2 for the two directions.
Solution
dp[mask][v] = number of simple paths that start at the lowest vertex of mask, visit exactly mask, and end at . Only extend to vertices larger than the start. Whenever is adjacent to the start and the path has at least 3 vertices, it closes a cycle. Each cycle is found twice (once per direction).
def count_simple_cycles(n, edges):
adj = [0] * n
for a, b in edges:
adj[a] |= 1 << b
adj[b] |= 1 << a
dp = [[0] * n for _ in range(1 << n)]
for v in range(n):
dp[1 << v][v] = 1
total = 0
for mask in range(1, 1 << n):
start = (mask & -mask).bit_length() - 1
for v in range(n):
ways = dp[mask][v]
if not ways:
continue
if bin(mask).count("1") >= 3 and (adj[v] >> start) & 1:
total += ways
for w in range(start + 1, n):
if (adj[v] >> w) & 1 and not (mask >> w) & 1:
dp[mask | (1 << w)][w] += ways
return total // 2
assert count_simple_cycles(4, [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]) == 7 # 4 triangles + 3 squares
12. Find the Shortest Superstring (LeetCode 943) — Shortest string containing each of words. Teaches Held–Karp on an asymmetric "overlap" matrix with reconstruction, and the path (not cycle) variant.
Hint
Cost of going from word to word = len(b) - overlap(a, b). Start from every word (path, free start), maximise total overlap, rebuild the order with parents, then glue the words.
13. Number of Ways to Wear Different Hats to Each Other (LeetCode 1434) — 40 hat types, at most 10 people; count ways for everyone to wear a different hat they like. Teaches choosing which side to put in the mask: the 10 people, not the 40 hats.
Hint
Iterate hats as the "time" axis; dp[peopleMask] = ways so far. For each hat, either nobody wears it or one person in its list who is not yet in the mask does. steps.
Common mistakes & interview follow-ups
"Why is it states and not ?" Because the future cost depends on where you stand. Two partial tours with the same set but different endpoints are not comparable. In the assignment problem the "where" is implied by the popcount, so is enough there.
"Can you reduce the memory?" Drop city 0 from the mask (×½). Use 32-bit costs. Recompute parents instead of storing them. Process masks by popcount layers and keep only two layers — but then you lose the table needed for reconstruction, so reconstruct by re-running or by storing parents compactly (one byte per state).
"The interviewer says ." Bitmask DP is out (). Ask about structure: is it an assignment with additive costs (Hungarian, min-cost flow)? A metric TSP where 1.5-approximation is acceptable (Christofides)? A practical route where heuristics are fine? Or a subset-sum (meet in the middle)?
"Why does increasing numeric order work?" Every transition sets a bit that was 0, which strictly increases the integer. Prove it in one line; interviewers like hearing it.
"How do you print the tour?" Parent table, walk back from the best final city, remove each city's bit as you go, reverse.
"Count the paths instead of minimising." Replace min with + and INF with 0. Watch for overflow; use the modulus.
Mistakes interviewers watch for: forgetting to add the return edge to the start; using dp[1 << n][n] with and 64-bit ints in Python; precedence bugs in mask & 1 << j; off-by-one between "popcount" and "next worker index"; starting the TSP from every city and then adding the return edge to city 0 (mixes path and cycle variants).
Quick quiz
1. In the 4-city trace, why is there no state with mask 0110?
Answer
Every path starts at city 0, so every reachable mask contains bit 0. 0110 = {1, 2} does not.
2. dp[1111][3] had two candidates of value 75. Does it matter which parent is stored?
Answer
No. Both give a valid path of cost 75 ending at city 3; the reconstruction returns one of the optimal paths. Here state (1111, 3) is not even on an optimal tour (75 + 20 = 95 > 80).
3. List the non-empty submasks of 0110 in the order the (s - 1) & mask loop produces them.
Answer
0110, 0100, 0010. (Then 0000, which ends the loop.)
4. Why is iterating all submasks of all masks and not ?
Answer
Each element is in one of three situations: outside the mask, inside the mask but outside the submask, or inside both. combinations. Equivalently .
5. In the assignment DP, why does dp[mask] not need a "which worker" index?
Answer
Workers are assigned in a fixed order, so after placing jobs the next worker is always worker = popcount(mask).
6. You need TSP for with 4-byte costs and 1-byte parents. Roughly how much memory, and how could you halve it?
Answer
states × 5 bytes ≈ 440 MiB. Dropping city 0 from the mask halves the masks and gives about MiB.
Further reading / sources
- Richard Bellman, "Dynamic programming treatment of the travelling salesman problem", Journal of the ACM 9(1), 1962.
- Michael Held and Richard M. Karp, "A dynamic programming approach to sequencing problems", Journal of the Society for Industrial and Applied Mathematics 10(1), 1962.
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed. — Chapter 14 (optimal substructure), Chapter 34–35 (NP-completeness of Hamiltonian cycle, TSP approximation), Problem 14-3 (bitonic TSP).
- Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer 2010 — Chapter 3 (dynamic programming over subsets, including TSP and Steiner tree) and Chapter 4 (inclusion–exclusion).
- Andreas Björklund, "Determinant sums for undirected Hamiltonicity", FOCS 2010.
- P. Griffiths Selinger et al., "Access Path Selection in a Relational Database Management System", SIGMOD 1979.
- Guido Moerkotte and Thomas Neumann, "Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products", VLDB 2006.
- PostgreSQL documentation, Genetic Query Optimizer and the
geqo_thresholdsetting. - David Applegate, Robert Bixby, Vašek Chvátal, William Cook, The Traveling Salesman Problem: A Computational Study, Princeton 2006 (Concorde).
- cp-algorithms, Enumerating submasks of a bitmask.
- AtCoder Educational DP Contest, problem list — problems O and U.
Lessons: previous — DAG DP · next — SOS DP · module — Dynamic Programming · course — DSA: Zero to Mastery.
Related Archon pages: Bit Manipulation · Euler & Hamiltonian Paths · Bipartite Matching & Hungarian · BFS in Depth · Shortest Paths · Broken-Profile DP · Grid & Path DP · Query Planning & Optimization.