Bitmask Dynamic Programming: State Compression, TSP & Hamiltonian Paths in O(N^2 2^N)

When a problem requires tracking subsets of elements with $N le 20$, Bitmask Dynamic Programming represents the subset as an integer binary bitmask, converting exponential combinatorial searches into structured dynamic programming transitions.

1. Essential Bitwise Manipulation Primitives

• (mask >> i) & 1: Check if element $i$ is in the subset.
• mask | (1 << i): Add element $i$ to the subset.
• mask ^ (1 << i): Remove element $i$ from the subset.
• __builtin_popcount(mask): Count total elements in the subset.

2. Travelling Salesperson Problem (TSP)

Let dp[mask][u] be the minimum cost to visit all vertices present in mask, ending at vertex u:

dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v]);