Bitmask DP: Solving Small-n Subset Problems Like the Travelling Salesman

When a problem has n ≤ 20 and asks about orderings or subsets ("visit every city once", "assign each worker one job"), the intended solution is often bitmask DP: represent the set of items already used as the bits of an integer.

Bit tricks you'll need

• mask & (1 << i): is item i in the set?
• mask | (1 << i): add item i.
• mask ^ (1 << i): remove item i (when present).
• sub = (sub - 1) & mask: iterate all submasks of mask.
• bin(mask).count("1") or mask.bit_count(): size of the set.

Held-Karp for the travelling salesman problem

State: dp[mask][v] = cheapest path that starts at city 0, visits exactly the cities in mask, and ends at v.

def tsp(dist):
    n = len(dist); FULL = 1 << n; INF = float("inf")
    dp = [[INF] * n for _ in range(FULL)]
    dp[1][0] = 0
    for mask in range(FULL):
        for v in range(n):
            if dp[mask][v] == INF or not mask >> v & 1:
                continue
            for u in range(n):
                if mask >> u & 1:
                    continue
                nm = mask | 1 << u
                dp[nm][u] = min(dp[nm][u], dp[mask][v] + dist[v][u])
    return min(dp[FULL - 1][v] + dist[v][0] for v in range(1, n))

Complexity: O(2^n · n²) time and O(2^n · n) memory, which is about 400 million simple steps at n = 20. Feasible in C++, tight in Python, and vastly better than n! brute force.

Other shapes of the same idea

• Assignment: dp[mask] = min cost when the first popcount(mask) workers are assigned to the jobs in mask: O(2^n · n).
• Partition into k equal-sum subsets: dp[mask] = current bucket fill after using the elements in mask.
• Submask enumeration: covering or grouping problems in O(3^n).
• Shortest path visiting all nodes: BFS over states (node, mask).

How to spot it fast

Small n (12 to 20), "each item used once", and an answer that depends on which items were used, not just how many. Say: "n is at most 16, so I'll use a bitmask over used items; there are 2^16 × 16 states, each with 16 transitions."

Disclosure: I work on Linkjob AI, an AI coding interview assistant. These are general practice notes.