Bitmask DP — TSP intro — Coding notes

WHY a bitmask?

The state and recurrence (derive from scratch)

HOW do we build it? Think about the last step. To be standing at $i$ having visited mask, you must have just arrived from some earlier city $j$ that is also in mask, $j\neq i$ , having visited mask minus $i$ . We minimise over all such $j$ :

Complexity (and the 80/20)

Worked example 1 — 3 cities by hand

Cities $0,1,2$ . Distances (symmetric): $\text{dist}[0][1]=10,\ \text{dist}[0][2]=15,\ \text{dist}[1][2]=20$ .

Base: dp[001][0] = dp[1][0] = 0.

Step	State	Compute	Why this step?
1	`dp[011][1]`	`dp[001][0]+dist[0][1] = 0+10 = 10`	Add city 1 from start. mask `011`={0,1}, last=1.
2	`dp[101][2]`	`dp[001][0]+dist[0][2] = 0+15 = 15`	Add city 2 from start.
3	`dp[111][2]`	`dp[011][1]+dist[1][2] = 10+20 = 30`	All visited, came from 1→2.
4	`dp[111][1]`	`dp[101][2]+dist[2][1] = 15+20 = 35`	All visited, came from 2→1.
5	Close	$\min(30+\text{dist}[2][0],\ 35+\text{dist}[1][0])$	Return to start.
		$\min(30+15,\ 35+10)=\min(45,45)=\mathbf{45}$	Tour cost = 45.

Both routes $0\to1\to2\to0$ and $0\to2\to1\to0$ cost 45 (symmetric triangle), so 45 is optimal. ✓

Worked example 2 — reading the bits

Suppose $n=4$ and you're computing dp[mask][3] with mask = 1011 (binary) $=11$ .

Why this step? Bit 3 of 1011 is 1? 1011 → bits are (3210)=1011, bit3=1 ✓ so city 3 is allowed as the endpoint.
prev = mask & ~(1<<3) = 1011 & 0111 = 0011 $=\{0,1\}$ .
Why this step? We must have arrived at 3 from a city already in prev, so $j\in\{0,1\}$ .
dp[11][3] = min( dp[3][0]+dist[0][3], dp[3][1]+dist[1][3] ).

Reference implementation

INF = float('inf')
def tsp(dist):
    n = len(dist)
    dp = [[INF]*n for _ in range(1<<n)]
    dp[1][0] = 0                       # base: at 0, visited {0}
    for mask in range(1<<n):
        for i in range(n):
            if dp[mask][i] == INF:     # unreachable, skip
                continue
            for k in range(n):         # try going to city k next
                if mask & (1<<k):      # already visited -> skip
                    continue
                nm = mask | (1<<k)
                nd = dp[mask][i] + dist[i][k]
                if nd < dp[nm][k]:
                    dp[nm][k] = nd
    full = (1<<n)-1
    return min(dp[full][i] + dist[i][0] for i in range(1,n))

Note: this version pushes forward (mask → nm); the recurrence above pulls backward. Same DP, two iteration directions — both valid because masks only grow.

Common mistake Steel-manned traps

1. "Order matters, so I must store the sequence." Feels right because tours obviously have an order. Fix: only the visited set + current city affect the remaining cost; the prefix's internal order is already optimised inside the dp value. Storing order would re-explode to $n!$ .

2. Forgetting bit $i$ must be set in mask for dp[mask][i]. Feels right to loop all $i$ . Fix: if city $i$ isn't visited, "ending at $i$ " is meaningless — that state stays $\infty$ . Guard with if mask & (1<<i).

3. Forgetting the return edge. Feels right because dp already visited everything. Fix: TSP is a cycle; add + dist[i][0] at the end. Skip it only if you wanted a Hamiltonian path.

4. Operator precedence. mask & 1<<i works (shift binds tighter), but mask & 1 == 0 does not (== binds tighter than &). Always parenthesise: (mask & x) == 0.

Recall Feynman: explain to a 12-year-old

Imagine you must visit every friend's house once and come home, using the least walking. Instead of remembering the whole path you took, you only jot down two things on a sticky note: which houses you've already been to (tick boxes) and whose house you're standing in right now. If two different walks led you to the same "tick boxes + current house," they're the same from now on — so you keep only the cheaper one and throw the other away. Those sticky notes are the bitmask. Throwing away duplicates is why it's fast.

Active recall

What does dp[mask][i] store in TSP bitmask DP?

Min cost of a path starting at city 0, visiting exactly the set mask, and ending at city i (bit i set in mask).

Why does bitmask DP beat the

n!

brute force?

It collapses all orderings that reach the same (visited-set, current-city) into one state, giving

O(n^2 2^n)

instead of

O(n!)

What is the base case?

dp[1][0] = 0 (only city 0 visited, standing at 0, cost 0); everything else

\infty

Write the transition.

dp[mask][i] = min over j in prev of dp[prev][j] + dist[j][i], where prev = mask & ~(1<<i).

How do you get the final closed-tour answer?

min over i!=0 of dp[(1<<n)-1][i] + dist[i][0].

How do you test if city i is in mask?

mask & (1<<i) is non-zero.

How do you remove city i from mask?

mask & ~(1<<i).

Time and space complexity?

Time

O(n^2 2^n)

, space

O(n 2^n)

Why must bit i be set in mask for dp[mask][i] to be valid?

"Ending at i" requires i to have been visited; otherwise the state is impossible and stays

\infty

What changes if you want a Hamiltonian path instead of a cycle?

Drop the +dist[i][0] return term; answer becomes min_i dp[full][i].

Connections

Dynamic Programming — state, optimal substructure, overlapping subproblems.
Travelling Salesman Problem — the NP-hard problem this solves exactly for small $n$ .
Held-Karp Algorithm — the formal name of this exact DP.
Bit Manipulation — masks, shifts, and-not.
Subset Enumeration — iterating over $2^n$ subsets.
Hamiltonian Path and Cycle — what a valid tour is.
Branch and Bound — alternative exact method for larger $n$ .

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, TSP ka matlab hai: ek city se start karo, saari cities exactly ek baar visit karke wapas ghar aao, aur total distance minimum ho. Brute force me saare $n!$ orders try karne padte hain — 12-13 city ke baad hi laptop hang. Bitmask DP ka jugaad ye hai: future ke liye sirf do cheezein important hain — kaun kaun si cities visit ho chuki hain aur abhi tum kahan ho. Order ki internal detail matter nahi karti, kyunki uska best cost dp value me already chhupa hua hai.

"Visited cities ka set" ko hum ek integer ke binary bits me store karte hain — isi ko bitmask kehte hain. Bit $i$ = 1 matlab city $i$ visit ho gayi. State banta hai dp[mask][i] = city 0 se shuru karke, exactly mask set visit karke, abhi city $i$ par khade ho — uska minimum cost. Transition simple: city $i$ par pahunchne se pehle kisi city $j$ par the (jo prev = mask minus $i$ me ho), to dp[mask][i] = min over j ( dp[prev][j] + dist[j][i] ).

Complexity ban jaati hai $O(n^2 2^n)$ — exponential to hai, par $n!$ se crores guna fast. $n \le 20$ tak comfortably chalta hai. Yahi 80/20 point hai: yaad rakho ki SET + SPOT do hi indices chahiye, aur end me ghar wapas aane ke liye + dist[i][0] add karna mat bhoolna. Bas itna pakka kar liya to TSP intro clear.

Bitmask DP — TSP intro

WHY a bitmask?

The state and recurrence (derive from scratch)

Complexity (and the 80/20)

Worked example 1 — 3 cities by hand

Worked example 2 — reading the bits

Reference implementation

Active recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Algorithm Paradigms

Connections