Vibe Engines Learn
Algorithms · Dynamic Programming

Sets as Integers.

Some problems have a state that is a set — “which cities have I visited?” The trick that makes them tractable is representing that set as the bits of an integer: with n items, a subset is a number from 0 to 2ⁿ−1, and set operations become fast bitwise ops. Bitmask DP then dynamic-programs over states like (subset, current position). On the traveling salesman problem this is the Held–Karp algorithm: O(2ⁿ·n²) instead of the brute-force O(n!) — still exponential, but astronomically smaller for real n. Step through the subsets and watch the optimal tour assemble.

TSP in O(2ⁿ·n²) vs O(n!) · a subset = the bits of an integer · state = (visited-set, position)
bitmask

An integer whose bit i means “item i is in the set.” 0b01011 = {0,1,3}.

state

Here (mask, last): the set of visited cities, and which one we’re standing on.

transition

From (mask, last), go to an unvisited city j: (mask | 1<<j, j).

Held–Karp

The bitmask-DP solution to TSP: O(2ⁿ·n²) time, O(2ⁿ·n) space.

held-karp.js — a subset is a number
Ready
Five cities; find the shortest tour from city 0 back to city 0. The DP state is (visited-set, last city), and the visited-set is stored as a 5-bit mask. We fill subsets from small to large. Step through them.
00001
current mask
0
states filled
–
best tour

How it works

The brute-force TSP tries all (n−1)! orderings — hopeless past a dozen cities. Held–Karp’s insight is that two partial tours visiting the same set of cities and ending at the same city are interchangeable going forward: only the cheapest one can matter. So define dp[mask][i] = the cheapest way to start at city 0, visit exactly the cities in mask, and end at city i. Fill masks from smallest to largest; each state extends by adding one unvisited city. There are 2ⁿ·n states and each looks at n transitions, giving O(2ⁿ·n²). For n = 15 that’s about 7 million operations versus 15! ≈ 1.3 trillion — the difference between instant and never.

1

Encode the visited set as bits

With n cities, the set of visited ones is an n-bit integer: bit i set means city i is visited. Adding a city is mask | (1<<city); testing is mask & (1<<city).

2

Define the state

dp[mask][i] = minimum cost to start at city 0, visit exactly the cities in mask, and currently be at city i. Base case: dp[{0}][0] = 0.

3

Fill masks small to large

For each state (mask, i), try going to each unvisited city j: dp[mask | 1<<j][j] = min(…, dp[mask][i] + dist(i, j)). Because you only add bits, larger masks depend only on smaller ones.

✓

Close the tour

Once the full mask (all cities) is reached, add the edge back to city 0: answer = min over i of dp[full][i] + dist(i, 0). Reconstruct the path via stored choices.

TSP time
O(2ⁿ·n²)
vs brute force
O(n!)
States
2ⁿ · n
Set ops
bitwise

The code

# Held-Karp: exact TSP via bitmask DP, O(2^n * n^2) dp = [[inf]*n for _ in range(1<<n)] dp[1][0] = 0 # start at city 0, mask = {0} for mask in range(1<<n): for i in range(n): if dp[mask][i] == inf: continue for j in range(n): if mask & (1<<j): continue # j already visited nm = mask | (1<<j) # add city j to the set dp[nm][j] = min(dp[nm][j], dp[mask][i] + dist[i][j]) ans = min(dp[(1<<n)-1][i] + dist[i][0] for i in range(1, n))

Quick check

1. How is a subset of n items represented in bitmask DP?

2. In Held–Karp, what is the DP state?

3. How does Held–Karp compare to brute-force TSP?

FAQ

What is bitmask DP?

Dynamic programming where part of the state is a subset, encoded as the bits of an integer — making set membership, union, and iteration fast via bitwise ops, and letting you index a DP table by subset. It’s standard for problems with up to ~20 items whose state includes “which items are used.”

What is the Held–Karp algorithm?

The bitmask-DP solution to the traveling salesman problem: dp[mask][i] is the cheapest route starting at a fixed city, visiting exactly the cities in mask, ending at i, filled small-to-large. O(2ⁿ·n²) time, O(2ⁿ·n) space — the best known exact TSP algorithm, far faster than all n! tours.

What is the practical limit on bitmask DP?

The 2ⁿ factor makes it practical to about n = 20 (2²⁰ ≈ a million subsets, times n or n²). Beyond that it’s too large. For bigger TSP you switch to heuristics — nearest neighbor, 2-opt, simulated annealing — giving good but not provably optimal tours.

What other problems use bitmask DP?

Assignment problems (match n workers to n tasks), counting Hamiltonian paths, shortest superstring, broken-profile/plug DP on grids, subset-sum and partition variants, and many “use every item once” problems — whenever the state must remember an arbitrary subset of a small universe.

Keep going

Algorithm

Tree DP →
Algorithm

Knapsack →
Algorithm

Simulated Annealing →
Roadmap

The DSA Roadmap →
Finished this one? 0 / 98 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →