Bitmask DP & the Exact Tour
In short: when the rest of a route depends only on which stops are
already visited and where the van is now — never on the order it took to
get there — the set of done stops is the whole state, and a set of up to
about 20 items fits in the bits of one integer. dp[S][j] is the shortest
route that visits exactly the stops in set S and ends at j; filling it in
plain numeric order always has every smaller set ready first, because turning
on a bit only ever makes a number bigger.
The afternoon courier leaves the depot, drops parcels at a handful of stops and comes back. The streets are one-way, so going from stop 2 to stop 3 isn't the same distance as going from 3 to 2. With 4 stops there are 6 possible orders, and with 10 stops there are 362,880. Trying every order is fine today and too slow by next month. Guessing (always drive to the nearest unvisited stop) is fast, and it's often wrong by a lot.
Between those two there's an exact method that works well up to about 15 stops. It rests on one question: what does the rest of the route actually depend on? It doesn't depend on the order you've driven so far. It depends only on which stops are done and where the van is now.
A set is the state
Suppose two partial routes have both visited stops {0, 1, 3} and are both standing at stop 3. One took 14 km to get there and the other took 6. Whatever the best way to finish is, it's the same for both, because the same stops are left and the van is in the same place. So the 14 km route can never be part of the best tour, and you only need to remember the 6.
That gives the state:
dp[S][j]= the shortest route that starts at the depot, visits exactly the stops in setS, and ends at stopj.
To fill it, ask which stop came just before j. It was some k in S
other than j, and the route to k visited exactly S without j:
dp[S][j] = min over k of dp[S − {j}][k] + dist[k][j]
Then the full tour is min over j of dp[all][j] + dist[j][0].
Storing a set in an integer
A set of up to 20 stops fits in the bits of one integer, where bit i is on
when stop i is in the set. 0b1011 is the set {0, 1, 3}, read right to left.
Every set operation is then a single machine instruction:
| Set operation | Bit operation |
|---|---|
| the set of all n stops | (1 << n) - 1 |
is k in S? |
S & (1 << k) |
add k |
S | (1 << k) |
remove k |
S ^ (1 << k) (when k is in S) |
| how many stops | bin(S).count("1") |
Operator precedence catches people out, so check yourself:
mask = 0b1011
print(bin(mask | 1 << 2), mask >> 1 & 1, mask & (1 << 2))A mask is also just a number, and the most common bug is forgetting that:
0b1010 is the set {1, 3}, but this prints [2, 3]. Test stop k's own bit.
Watching the table fill
Four stops on one-way streets: dist = [[0, 2, 9, 10], [3, 0, 6, 4], [8, 7, 0, 3], [6, 4, 5, 0]],
where row a gives the distances from a. Rows are the sets that contain
the depot, smallest first. Columns are the stop the route ends at.
Each cell reads only rows with one bit fewer, which are all filled earlier. So filling by the number of stops visited always has the inputs ready.
The first row is the set {0}: the van is at the depot having driven 0 km. A "-" is impossible, because a route must end at a stop it has visited and only the first row can end at the depot. 8 by 4 table. At row 0, column 0 — value 0. 20 of 32 cells filled.
A route with n stops has 2ⁿ sets and n endpoints, so there are
2ⁿ · n cells, and each one looks at up to n predecessors. That's
O(2ⁿ · n²) time in all. Those 2ⁿ · n cells are also what the table
holds in memory, so it costs O(2ⁿ · n) space — honestly exponential in
both, just far smaller than listing every order outright. It's still
exponential, but it grows far more slowly than (n − 1)!:
import math
n = 12
print(2 ** n * n, math.factorial(n - 1))In what order?
The table needs every smaller set filled before any set that contains it. Sorting by the number of stops works, and so, conveniently, does plain numeric order, because adding a bit always makes the number bigger. Step through the size-sorted order for three stops:
Now fill the whole table yourself, with one row for every mask, including the ones without the depot, which stay at infinity. Change a distance and watch which cells move:
Your set table in numeric order. Every cell compares cells in a row with one bit fewer, and that row is always higher up the table.
Recovering the order
The table stores distances, so recover the tour by walking back, the way you
did for knapsack. Start from the best last stop j. Remove j from the set, and
find the k whose cell plus dist[k][j] gives exactly dp[S][j]. Repeat until
you reach the depot. On a symmetric map, going round clockwise and anticlockwise
always tie, so the task fixes a rule: the smallest-numbered stop wins every
tie.
The same trick on other sets
Anything whose future depends only on which things are done can use a mask. Here's a common interview shape, in its own words:
Interview-style problem: one job per driver.
ndrivers andnjobs.cost[d][j]is what it costs driverdto do jobj. Give every driver exactly one job and every job exactly one driver, at the lowest total cost.Constraints:
1 ≤ n ≤ 12.Examples:
[[4, 2, 8], [4, 3, 7], [3, 1, 6]]→12.[[5]]→5.
The state is the set of jobs already taken. If the jobs are handed out to drivers in order, the number of jobs taken is the next driver's number, so the driver doesn't need to be part of the state:
Your exercises use the same move four more times: counting job orders that respect "this before that", covering every licence type with the fewest drivers, pairing drivers two to a van, and a sweep that can start and end anywhere.
❓ Cross-question: "Why not just use a Python
setorfrozensetas the key?" You can, with a dict as the table, and it's a fine first version. An integer is much smaller and faster, though: it indexes a list directly, hashes instantly, and you get "all subsets in a valid order" for free fromrange(1 << n).
Where the wall is
Python in the browser manages roughly 10 million simple table steps a second, and the table costs n² · 2ⁿ steps:
| stops n | steps | at 10 million a second |
|---|---|---|
| 10 | 102,400 | 0.01 s |
| 12 | 589,824 | 0.06 s |
| 15 | 7,372,800 | 0.7 s |
| 16 | 16,777,216 | 1.7 s |
| 20 | 419,430,400 | 42 s |
Fifteen stops is the most that finishes within a second, and each stop after that more than doubles the work. That is why the exercises here stay at 12 or fewer. Beyond about 20 stops even a fast language runs out of time and memory, and that's where exact answers give way to approximations.
Idioms & real-world patterns
Fill order for free
for mask in range(1 << n) visits every set after all of its subsets. You
rarely need to sort by size, except when a picture reads better that way, as
the one above does.
⚡ Advanced: enumerating submasks
Some set DPs split a set S into two parts, for example "which stops go on van
A, and the rest on van B". The loop sub = S; while sub: ...; sub = (sub - 1) & S
visits every non-empty submask of S. Over all S together that's 3ⁿ steps
rather than 4ⁿ, which is what makes "split the set" DPs practical for about 12
to 14 items.
Quick practice
mask = 0b0110
print(bin(mask ^ (1 << 1)), bin(mask | (1 << 3)), bin(mask & (mask - 1)))The shortest round trip is 10 km, but this prints inf because the base case — "starting at the depot alone costs 0" — is missing. Add it back.
🎯 Your turn
Write best_tour(dist). dist[a][b] is the km from a to b, and stop 0 is the
depot. Find the shortest round from the depot through every stop exactly once
and back. Return {"km": total, "order": [0, …, 0]}.
best_tour([[0, 2, 9], [4, 0, 3], [5, 8, 0]])→{"km": 10, "order": [0, 1, 2, 0]}
Ties: the last stop is the smallest j with the lowest
dp[full][j] + dist[j][0]. Walking back, each earlier stop is the smallest k
that reproduces the cell exactly.
Then press ▶ Run, tap the Live App try chips, and hit ✓ Check. Green means the exact tour is built. ✅