When a problem is about choosing an order or a grouping of a few items, the state can be the set of items already used. With n items there are 2ⁿ sets (2ⁿ is n twos multiplied together). That is far fewer than the n! orders (n × (n − 1) × … × 1), and each set fits in one whole number.
A set as the state
BITS-5 wrote a set of items 0 to n − 1 as a mask: a whole number whose place k is 1 when item k is in the set. mask >> k & 1 asks whether k is in, mask | 1 << k adds it, and mask ^ 1 << k removes it (when it is in). Masks are list indices, so a table best[mask] is a plain list of length 2ⁿ.
Adding an item to a set makes the number larger. So the plain order for mask in range(1 << n) handles every set after all of its subsets: a topological order of the state DAG (lesson 2), with no extra work.
The shortest round trip
A salesperson starts at city 0, visits every city once and comes back. What is the shortest round trip? This is the travelling salesman problem. Trying every order of the other n − 1 cities costs (n − 1)! tours. But to continue a route well, you only need to know which cities it has visited and where it is now, not the order it took. That is the state, from Bellman, and Held and Karp (1962):
The rule looks at the city before j: best[mask][j] is the smallest best[mask without j][i] + d[i][j] over the cities i in the mask. The start is best[{0}][0] = 0, and the tour is the smallest best[all][j] + d[j][0]. In the figure the masks are written in binary, city 0 at the right.
Four cities, 0 to 3, and the distances between them (right). Find the shortest round trip from city 0 through every city and back. A state is a set of visited cities, written as a mask (place k is city k, place 0 at the right), and the city where the route ends.
def shortest_tour(d):
n = len(d)
INF = float("inf")
best = [[INF] * n for _ in range(1 << n)]
best[1][0] = 0 # at city 0, only city 0 visited
for mask in range(1, 1 << n, 2): # odd masks: city 0 is in the set
for j in range(n):
here = best[mask][j]
if here == INF:
continue
for k in range(n): # go on to a city k not yet visited
if not mask >> k & 1:
nxt = mask | 1 << k
if here + d[j][k] < best[nxt][k]:
best[nxt][k] = here + d[j][k]
full = (1 << n) - 1
return min(best[full][j] + d[j][0] for j in range(n))
This version pushes: from each finished state it offers a step to every unvisited city. It skips even masks, which do not contain the start, so it does half the work.
Subsets instead of orders
Why is it right? Take the shortest route through a set that ends at j, and remove its last step i → j. What is left is a route through the set without j, ending at i. If a shorter such route existed, it could replace this part and give a shorter route to j. So the best route to (mask, j) is made of a best route to some (mask without j, i): exactly what the rule tries.
Cost. There are 2ⁿ · n states, each tried from up to n cities: O(2ⁿ · n²) time and O(2ⁿ · n) memory. For 20 cities that is about 400 million steps against about 1.2 × 10¹⁷ orders. Exponential still, but the problem is NP-hard (HARD-1), so nothing polynomial is known, and this has been the best known worst-case method since 1962.
The same idea fits any problem where only which items are used matters, plus a little more (where you are, how full the current wagon is). Orders that differ only in what is already finished are merged into one state.
Jobs for people
n people, n jobs, and a cost for each person doing each job. Give each person one job, as cheaply as possible. If people are placed in order 0, 1, 2, …, the mask of jobs taken also tells you who is next: the number of 1s in it. So one number per mask is enough:
def cheapest_assignment(cost): # cost[p][j]: person p does job j
n = len(cost)
best = [float("inf")] * (1 << n)
best[0] = 0
for mask in range(1 << n):
p = mask.bit_count() # people 0 .. p-1 have jobs: place p next
if p == n:
continue
for j in range(n):
if not mask >> j & 1: # job j is still free
nxt = mask | 1 << j
best[nxt] = min(best[nxt], best[mask] + cost[p][j])
return best[-1]
O(2ⁿ · n). int.bit_count() (Python 3.10 and later) counts the 1s in C. For this problem there is also a polynomial method, the Hungarian method, O(n³) (n · n · n), related to matching (FLOW-5); SciPy has it as linear_sum_assignment. The mask version is the better choice when the rules are unusual, such as costs that depend on which jobs are already done.
Splitting into groups
Some problems split all the items into groups, where each group must be allowed (a weight limit, no two enemies together), and ask for the fewest groups. Here the last step adds a whole group, a submask of the items left. BITS-5’s loop sub = (sub - 1) & mask lists every submask.
def fewest_groups(n, ok): # ok(mask): can these items form one group?
good = [ok(m) for m in range(1 << n)]
best = [0] + [n + 1] * ((1 << n) - 1)
for mask in range(1, 1 << n):
low = mask & -mask # the lowest item is in some group
sub = mask
while sub: # every submask, largest first
if sub & low and good[sub]:
best[mask] = min(best[mask], best[mask ^ sub] + 1)
sub = (sub - 1) & mask
return best[-1]
The test sub & low asks only for groups that contain the lowest item left. Some group must contain it, so nothing is lost, and the same split is not found once per order of its groups.
3ⁿ grows much faster than 2ⁿ · n: for 16 items it is about 43 million against about a million. When groups are filled one at a time, as wagons are loaded one after another, a state of (set loaded, room left in the current group) avoids submasks altogether. That is the practice problem.
How far Python goes
Pure Python does roughly 10 to 30 million simple steps a second, and the browser is slower. So 2ⁿ · n work suits n up to about 18 or 20, 2ⁿ · n² about 15 to 17, and 3ⁿ about 14. Small habits help: test bits with mask >> k & 1 rather than building sets; keep tables as flat lists; skip states that cannot be reached (INF); and walk only the items that are in, or out of, a mask when that is the shorter list.
Now try ADDP-P4, The fewest wagons.
ADDP-4 counts as completed once you step through the figure to the last step.