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

When optimization problems demand tracking subsets or permutations of elements where N ≤ 20, Bitmask Dynamic Programming transforms exponential combinatorial searches into structured state-compressed algorithms. By packing boolean subset memberships into integer binary words, algorithms achieve single-cycle bitwise state transitions and conquer NP-hard challenges like the Travelling Salesperson Problem (TSP) in O(N^2 2^N) time.

1. Bitwise State Compression Foundations

In set-based optimization, representing subset states with standard data structures like std::set or hash tables introduces heavy heap allocations, pointer indirection, and hash collision overhead. In state compression, a subset S ⊆ {0, 1, ..., N - 1} is represented as an integer mask ∈ [0, 2^N - 1] where the i-th binary bit represents whether element i is included:

Query & Insertion

Test: (mask >> i) & 1
Set: mask | (1 << i)
Clear: mask & ~(1 << i)

Low-Bit & Population

Lowest bit: mask & (-mask)
Drop lowest: mask & (mask - 1)
Popcount: __builtin_popcount(mask)

2. The Travelling Salesperson Problem (TSP): Held-Karp Algorithm

The Travelling Salesperson Problem asks for the minimum cost Hamiltonian cycle visiting every city exactly once and returning to the origin. The brute-force permutation search requires O(N!) time:

For N = 20, 20! ≈ 2.43 × 10^{18} operations (takes thousands of CPU years).
Held-Karp Bitmask DP executes in N^2 × 2^N ≈ 400 × 1,048,576 ≈ 4.19 × 10^8 operations (completes in ~300ms!).

We define dp[mask][u] as the minimum path cost to visit exactly the subset of cities in mask, ending at city u:

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

    (where (mask & (1 << v)) == 0 and (mask & (1 << u)) != 0)

C++ Held-Karp TSP Implementation

const int INF = 1e9;
int tsp(int n, const vector<vector<int>>& dist) {
    int totalMasks = 1 << n;
    vector<vector<int>> dp(totalMasks, vector<int>(n, INF));
    dp[1][0] = 0; // Start at city 0

    for (int mask = 1; mask < totalMasks; ++mask) {
        for (int u = 0; u < n; ++u) {
            if (dp[mask][u] == INF) continue;
            for (int v = 0; v < n; ++v) {
                if (!(mask & (1 << v))) { // City v not visited
                    int nextMask = mask | (1 << v);
                    dp[nextMask][v] = min(dp[nextMask][v], dp[mask][u] + dist[u][v]);
                }
            }
        }
    }

    int minTour = INF;
    int fullMask = totalMasks - 1;
    for (int u = 1; u < n; ++u) {
        minTour = min(minTour, dp[fullMask][u] + dist[u][0]); // Return to 0
    }
    return minTour;
}

3. Efficient Submask Enumeration in O(3^N)

Many graph partitioning and set cover problems require iterating over all submasks sub ⊆ mask. The naive approach of iterating sub from 0 to 2^N - 1 and testing (sub & mask) == sub results in O(4^N) runtime.

The optimal bitwise decrement idiom enumerates strictly valid submasks:

    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {

        // Process submask 'sub'

    }

By subtracting 1 from sub and applying bitwise AND with mask, the processor skips all integers that contain bits not in mask. Across all masks, the total number of operations is:

    ∑_{k=0}^N &binom;{N}{k} × 2^k = (1 + 2)^N = 3^N
  

For N = 15, 4^{15} ≈ 1.07 × 10^9 (TLE), whereas 3^{15} = 14,348,907 (completes in ~15ms).

4. Memory Layout & Cache Locality Optimization

Because Bitmask DP tables hold 2^N × N integers, memory layout dictates CPU cache performance:

Dimension Ordering: Declare arrays as dp[1 << N][N] rather than dp[N][1 << N]. During transitions, the inner loop iterates over nodes u and v for a fixed mask, loading contiguous 64-byte L1 cache lines.
Flat Contiguous Allocation: Avoid vector-of-vectors (vector<vector<int>>) which introduces pointer indirections. Allocate a flat 1D buffer vector<int> dp((1 << N) * N) and index with (mask * N) + u.

5. The Assignment Problem: Bipartite Matching via Bitmask DP

Consider allocating N tasks to N workers, where worker i performing task j incurs cost cost[i][j]. While the Hungarian Algorithm solves this in O(N^3) for arbitrary N, Bitmask DP provides an elegant O(N 2^N) formulation that easily incorporates non-linear side constraints (e.g., worker exhaustion or prerequisite tasks):

    Let worker = __builtin_popcount(mask).

    dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + cost[worker][j])

Notice that the worker index is implicitly deduced from the number of bits already set in mask! This collapses a two-dimensional state dp[worker][mask] into a one-dimensional array of size 2^N, halving memory consumption and guaranteeing strict topological processing by iterating masks from 0 to 2^N - 1.

6. Algorithmic Complexity Comparison Matrix

Problem Archetype	Brute Force	Bitmask DP Time	Space Complexity	Feasible Upper Bound
Travelling Salesperson (TSP)	O(N!)	O(N^2 2^N)	O(N 2^N)	N ≤ 20 - 22
Submask Enumeration	O(4^N)	O(3^N)	O(2^N)	N ≤ 15 - 16
Hamiltonian Path Check	O(N!)	O(N^2 2^N)	O(N 2^N)	N ≤ 22
Bipartite Matching	O(N!)	O(N 2^N)	O(2^N)	N ≤ 24

6. Key Engineering Invariants

Bit Shift Overflow: Always cast literals to 64-bit integers when N > 31: use 1ULL << i to prevent undefined 32-bit signed overflow.
Popcount Order Sorting: When problem transitions require submasks to be processed strictly by subset cardinality, iterate masks sorted by __builtin_popcount(mask) or group states into buckets.
Meet-in-the-Middle: When N ∼ 40, partition the elements into two halves of N / 2 ∼ 20, run Bitmask DP on both halves independently, and merge with two pointers in O(2^{N/2}) time.