• 1 ≤ n ≤ 20
• 0 ≤ dist[i][j] ≤ 10⁶
• Every city must be visited exactly once and the tour must return to the start
• Costs need not be symmetric: dist[i][j] may differ from dist[j][i]

Start at city 0, visit every other city exactly once, come back. Minimise the total distance. Simple to state, and one of the most studied hard problems in computing — no method is known that solves it in polynomial time, and finding one would settle the biggest open question in the field.

So the goal here is not a fast solution; it is the best exponential solution, which turns a factorial into something merely exponential. With n ≤ 20, that difference is the difference between impossible and instant.

Note the costs may be asymmetric — going from A to B need not cost the same as B to A — so you cannot assume any symmetry to save work.

Fix city 0 as the start. Then a tour is an ordering of the other n-1 cities, so there are (n-1)! tours. For n = 20 that is 19!, roughly 1.2 × 10¹⁷. At a billion tours per second, several years.

Where is the waste? Consider two different partial tours: 0 → 3 → 5 → 2 and 0 → 5 → 3 → 2. They took different routes, but they have visited exactly the same set of cities and they are both standing in city 2. From here on, the cheapest way to finish is identical for both — the future does not care in what order the past happened, only which cities are used up and where you are now.

Brute force recomputes that shared future separately for every ordering that reaches the same situation. That is enormous duplication, and it is exactly the opening these tables exploit.

State Definition: f(mask, city) is the minimum cost to start at city, visit every city not yet in mask, and return to city 0 — where mask records the set of cities already visited.

The new idea is how to hold a set in a table index. A subset of at most 20 cities can be written as a 20-bit binary number: bit i is 1 if city i has been visited and 0 if not. That is a bitmask, and it is just an integer, so it can index an array directly.

The operations you need are three, and each is one instruction:

With n = 20 there are 2²⁰ ≈ one million possible masks and 20 possible current cities, giving about 20 million states. Each state tries up to 20 next cities, so roughly 400 million simple operations — heavy but feasible, and unimaginably better than 10¹⁷.

The recurrence is the natural one: from the current city, try every unvisited city as the next stop.

f(mask, city) = min over unvisited next of [ dist[city][next] + f(mask | (1 << next), next) ]

Base case: when mask contains every city, the tour is complete and only the trip home remains, so f = dist[city][0].

The answer is f(1, 0) — mask 1 means only city 0 has been visited, and we are standing in city 0.

def tsp(dist):
    n = len(dist)
    FULL = (1 << n) - 1                 # every city visited
    INF = float('inf')
    memo = {}

    def f(mask, city):
        if mask == FULL:
            return dist[city][0]                    # go home
        if (mask, city) in memo: return memo[(mask, city)]

        best = INF
        for nxt in range(n):
            if mask & (1 << nxt):                   # already visited
                continue
            cost = dist[city][nxt] + f(mask | (1 << nxt), nxt)
            best = min(best, cost)

        memo[(mask, city)] = best
        return best

    return f(1, 0)                                  # start in city 0, only it visited

The bottom-up version fills masks in decreasing order, because f(mask, ...) depends on masks with strictly more bits set — and adding a bit always makes the integer larger:

def tsp(dist):
    n = len(dist)
    FULL = (1 << n) - 1
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]

    for city in range(n):
        dp[FULL][city] = dist[city][0]              # base case: everything visited

    for mask in range(FULL - 1, 0, -1):
        for city in range(n):
            if not (mask & (1 << city)):            # we must be standing somewhere visited
                continue
            best = INF
            for nxt in range(n):
                if mask & (1 << nxt):
                    continue
                nxt_cost = dp[mask | (1 << nxt)][nxt]
                if nxt_cost != INF:
                    best = min(best, dist[city][nxt] + nxt_cost)
            dp[mask][city] = best

    return dp[1][0]

dist = [[ 0, 10, 15, 20],
        [10,  0, 35, 25],
        [15, 35,  0, 30],
        [20, 25, 30,  0]]

Only three orderings of cities 1, 2, 3 matter (each tour and its reverse cost the same here, since this matrix happens to be symmetric):

Answer 80.

Follow one state to see the machinery. f(0b1011, 3) means cities 0, 1 and 3 are visited and we stand in city 3. Only city 2 remains, so the cost is dist[3][2] + f(0b1111, 2) = 30 + dist[2][0] = 30 + 15 = 45. And f(0b0011, 1) — cities 0 and 1 visited, standing in city 1 — tries city 2 (35 + f(0b0111, 2)) and city 3 (25 + f(0b1011, 3) = 25 + 45 = 70), keeping the cheaper. That 45 is reused by every partial tour that arrives at the same situation, which is precisely the saving over brute force.

The signal for this technique is specific and easy to spot: the state needs to remember a set of things already used, and the number of things is small — roughly 20 or fewer. That size limit is not a coincidence; it is the constraint telling you the intended solution. If a problem caps n at 20 or so when the natural approach is factorial, a bitmask table is almost certainly what is wanted.

Common instances: assigning n jobs to n workers at minimum cost, counting the ways to pair people up, covering a board with dominoes column by column, choosing an ordering of tasks with prerequisites and switching costs, or partitioning items into groups that each satisfy some rule.

Two habits to take away.

A set can be an array index. Whenever "which ones have I already used?" belongs in your state and the universe is small, reach for an integer mask before reaching for a hash of sets — it makes the table a plain array and the transitions single instructions.

Read the constraints as a hint about the technique. N up to 20 with a factorial-looking problem means bitmask. N up to a few hundred with an interval-looking problem means an O(N³) interval table. N up to 100000 means something linear or logarithmic. The bounds are not decoration; they are the clearest signal the problem gives you about which of these tools you are expected to reach for.