Bitmask Dynamic Programming

Bitmask DP stores a subset as bits of an integer, allowing exponential problems to reuse equivalent histories. Held–Karp solves the small Traveling Salesperson Problem: start at city 1, visit each city exactly once, and return to 1 with minimum cost. Different visit orders that have the same visited set and final city have identical remaining choices, so only the cheapest such prefix is needed. This reduces factorial permutation search to O(n²2ⁿ).

Prerequisites: Basic dynamic programming; bit operations; adjacency/cost representations. Difficulty: Advanced.

Build the idea

1. 1. Represent membership with bits

   Internally city i uses bit i, with cities numbered 0..n−1 for shifts. Test membership by mask & (1<<i), insert with mask | (1<<i), and remove a known member with mask ^ (1<<i). The complete set is (1<<n)−1. User-facing city 1 is internal index 0. A bitmask is a set, not an ordering: the extra last-city state retains the order information relevant for the next edge.

2. 2. Give dp an exact meaning

   dp[mask][v] is the cheapest path starting at city 1, visiting exactly mask, and ending at v. Initially only dp[1][0]=0 is possible. Every other entry is INF, meaning unreachable; initializing all entries to zero would invent free paths. If u is unvisited and edge v→u exists, relax dp[mask∪{u}][u] using dp[mask][v]+cost[v][u]. Adding a bit increases the numeric mask, so increasing-mask iteration is valid.

3. 3. Work a three-city example

   For the symmetric matrix with costs 1→2=10, 1→3=15, 2→3=20, state mask 011 ending at city 2 costs 10, and mask 101 ending at city 3 costs 15. Extending produces full-mask costs 30 ending at city 3 and 35 ending at city 2. Return edges cost 15 and 10 respectively, so either cycle costs 45.

   Visited mask	Final city	Best prefix cost
   001	1	0
   011	2	10
   101	3	15
   111	3	30
   111	2	35

4. 4. Finish the tour separately

   The transition loop deliberately never re-enters start city 1. After all bits are set, add an existing edge back to 1 and minimize over final cities. Without this closing step the problem is a Hamiltonian path rather than a tour. Missing directed edges are encoded −1; all actual costs are nonnegative. A one-city instance is defined to cost zero, independent of its diagonal entry.

5. 5. Understand the correctness and limit

   An optimal nonempty path has some last edge v→u. Removing it leaves an optimal prefix for the smaller visited set and last vertex v; otherwise a cheaper equivalent prefix would improve the whole route. The transition enumerates every such predecessor. There are n2ⁿ states and up to n extensions each. For n=18, long-long storage alone is about 36 MiB; doubling n by one roughly doubles memory. Bit operations do not make exponential state counts cheap.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<limits>
#include<algorithm>
using namespace std;
using ll=long long;
int main(){
    int n;
    if(!(cin>>n)){
        return 0;
    }
    vector<vector<ll>>cost(n,vector<ll>(n));
    for(auto&row:cost){
        for(ll&x:row){
            cin>>x;
        }
    }
    if(n==1){
        cout<<0<<'\n';
        return 0;
    }
    const ll INF=numeric_limits<ll>::max()/4;
    int states=1<<n;
    vector<ll>dp((size_t)states*n,INF);
    auto at=[&](int mask,int last)->ll&{
        return dp[(size_t)mask*n+last];
    };
    at(1,0)=0; // Start at city 1 (internal index 0).
    for(int mask=1;mask<states;++mask){
        if(mask&1){
            for(int v=0;v<n;++v){
                if((mask&(1<<v))&&at(mask,v)!=INF){
                    for(int u=1;u<n;++u){
                        if(!(mask&(1<<u))&&cost[v][u]!=-1){
                            int next=mask|(1<<u);
                            at(next,u)=min(at(next,u),at(mask,v)+cost[v][u]);
                        }
                    }
                }
            }
        }
    }
    ll answer=INF;
    for(int v=1;v<n;++v){
        if(cost[v][0]!=-1&&at(states-1,v)!=INF){
            answer=min(answer,at(states-1,v)+cost[v][0]);
        }
    }
    cout<<(answer==INF?-1:answer)<<'\n';
}

Complexity analysis

O(n²2ⁿ) time and O(n2ⁿ) memory. Flattened storage avoids per-mask vector overhead but does not change the exponential bound. Input is deliberately limited to 1≤n≤18; existing edge costs are 0..10^9, so tour totals fit long long. Reconstruction would require additional predecessor state or recomputation.

Example input and output

Read n (1..18) and an n×n directed cost matrix. −1 denotes a missing edge; other costs are 0..10^9. Print the minimum tour cost from city 1 visiting each city once and returning, or −1 if impossible. A one-city tour costs 0.

Input

3
0 10 15
10 0 20
15 20 0

Output

45

Tours 1→2→3→1 and 1→3→2→1 both cost 45.

Practical applications

Use for Hamiltonian paths, small assignment DP, visiting checkpoints and subset-dependent transitions. Meet in the middle works better when two independent halves can be joined cheaply. When graph size is large but there are only k special locations, shortest-path preprocessing plus subset DP on those k locations may help, provided the original visitation rules permit that reduction.

Check your understanding

Which state is sufficient for Held–Karp?

Put it into practice

Add predecessor tracking to reconstruct one minimum tour.