Bitmask DP — TSP intro: Foundations — Coding deep dive

Before you can read the parent note, you must own every piece of notation it throws at you. This page builds each one from absolute zero — plain words first, then the picture, then why the topic needs it. Read top to bottom; each block leans on the one above.

0. What problem are we even solving?

Look at the picture below. There are 4 dots (cities) joined by lines (roads). The red loop is one possible tour; there are many others. We want the cheapest loop among all of them.

1. $n$ — the number of cities

The picture: $n$ dots on paper. Naming them $0.. n - 1$ instead of "Paris, Rome…" is not laziness — it means a city's name is an index we can plug straight into an array. That habit is what makes the code short.

Why the topic needs it

every loop and every array size below is written in terms of

n

2. $dist [i] [j]$ — the cost table

Picture a spreadsheet: cell (row $i$ , col $j$ ) holds one road's price. The parent's 3-city example filled in dist[0][1]=10 and so on.

3. Sets, and why "which cities visited" is a set

Why the topic needs it

the set is one of the two indices of the DP table.

4. Binary digits — turning a set into one integer

Here is the trick that names the whole technique. We need to use a set of cities as an array index, and array indices must be plain integers. How do we squeeze a set into a single number?

Why the topic needs it

an integer is the cheapest possible array index, and there are exactly

2^{n}

of them for

n

cities — the second index of the DP table.

5. $2^{n}$ and $2^{n} - 1$ — how many masks, and "all visited"

6. The bit operations — how we read and edit a mask

We picture a mask as a row of light switches, one per city. These four moves are all we ever need. Here &, |, ~ act on each bit position independently.

See Bit Manipulation for these operators in full generality.

7. Iterating over subsets — where the masks come from

8. $min$ , $\infty$ , and "impossible states"

Why the topic needs it

the DP fills a table of minimums; slots we can't legally reach stay

\infty

and are silently ignored.

0.. n - 1

buy us?

A city's name is directly an array index, so cities plug straight into dist[i][j] and into bit

i

What does

dist [i] [j]

hold, and what shape is it?

The cost to go from city

i

to city

j

; a 2-D grid (spreadsheet), mirrored across the diagonal if roads are two-way.

Why do we store the set of visited cities instead of the full path order?

Future cost depends only on which cities are ticked plus your current spot; order is already optimised inside the dp value, so keeping it would re-explode to

n!

Convert visited set

{0, 2}

(with

n = 4

) to a mask integer.

Bits (3,2,1,0)=0101 = 5.

What is

1 ≪ i

The integer with only bit

i

set, equal to

2^{i}

Give the three edits: test / add / remove city

i

Test mask & (1<<i) non-zero; add mask | (1<<i); remove mask & ~(1<<i).

What integer is

full

and what set does it mean?

(1 ≪ n) - 1 = 2^{n} - 1

, binary all-ones — every city visited.

How many masks are there, and how do we visit them all?

2^{n}

of them; for mask in range(1<<n) — counting in binary enumerates every subset once.

Why do impossible states hold

\infty

They're unreachable placeholders; any real cost beats

\infty

in a

min

, so they never corrupt the answer.

State dp[mask][i] in one sentence.

Cheapest path starting at 0, having visited exactly mask, ending at city

i

(bit

i

must be set).

Foundations — Bitmask DP — TSP intro

0. What problem are we even solving?

1. $n$ — the number of cities

2. $dist [i] [j]$ — the cost table

3. Sets, and why "which cities visited" is a set

4. Binary digits — turning a set into one integer

5. $2^{n}$ and $2^{n} - 1$ — how many masks, and "all visited"

6. The bit operations — how we read and edit a mask

7. Iterating over subsets — where the masks come from

8. $min$ , $\infty$ , and "impossible states"

9. The DP table itself — `dp[mask][i]`

Prerequisite map

Equipment checklist