Bitmask DP

How to think about it

Bitmask DP is for problems where the state must remember which items are in the current set. A bitmask of n bits encodes membership: bit i is set if item i is used. The DP transitions add or remove an item by flipping a bit. The key constraint: n must be ≤ ~20 because the state space is 2^n - at n=20 that is one million states, feasible; at n=25 it is 33 million, borderline.

The canonical problem is TSP (traveling salesperson): dp[mask][last] is the min cost to visit the set of nodes in mask, ending at last. Transition: for each unvisited node j, dp[mask | (1<<j)][j] = min(dp[mask][last] + dist[last][j]). Base: dp[1<<start][start] = 0. Answer: min(dp[(1<<n)-1][last] + dist[last][start]) for the closed tour, or min(dp[full][last]) for open.

Template shapes

Shape	Core move	Example
TSP	dp[mask][last]; add unvisited j	LC 943
Assignment / partition	dp[mask]; try adding an item to a group	LC 1655, LC 1799
Subset selection with cost	dp[mask]; transition on subsets of remaining	LC 1994
Coloring / coloring constraints	dp[mask][color]; valid extensions	LC 1931

Complexity baseline

O(2^n * n) time, O(2^n * n) space (or O(2^n) if last is folded). At n=20, ~4 * 10^7 operations, fits in time. At n > 22, consider whether the problem admits a faster structure.

From template to problem

1. Confirm n ≤ ~20; if larger, look for a different technique (greedy, flow, meet-in-the-middle).
2. Define the mask: which items are “used” or “visited”.
3. Define the DP cell: dp[mask] or dp[mask][extra] (last node, count, group).
4. Iterate masks from small to large; for each, try adding each available item.
5. Extract the answer from the full mask or a min over the last dimension.

/** Bitmask DP template: TSP (open path) over a distance matrix. */

export function tspOpen(dist: number[][]): number {
  const n = dist.length;
  const full = (1 << n) - 1;
  const dp: number[][] = Array.from({ length: 1 << n }, () =>
    new Array<number>(n).fill(Infinity),
  );
  for (let i = 0; i < n; i++) dp[1 << i]![i] = 0;
  for (let mask = 1; mask <= full; mask++) {
    for (let last = 0; last < n; last++) {
      if (!(mask & (1 << last))) continue;
      const cur = dp[mask]![last]!;
      if (cur === Infinity) continue;
      for (let j = 0; j < n; j++) {
        if (mask & (1 << j)) continue;
        const next = mask | (1 << j);
        dp[next]![j] = Math.min(dp[next]![j]!, cur + dist[last]![j]!);
      }
    }
  }
  let ans = Infinity;
  for (let last = 0; last < n; last++) ans = Math.min(ans, dp[full]![last]!);
  return ans;
}

/** Bitmask DP template: TSP (open path) over a distance matrix. */

export function tspOpen(dist: number[][]): number {
  const n = dist.length;
  const full = (1 << n) - 1;
  const dp: number[][] = Array.from({ length: 1 << n }, () =>
    new Array<number>(n).fill(Infinity),
  );
  for (let i = 0; i < n; i++) dp[1 << i]![i] = 0;
  for (let mask = 1; mask <= full; mask++) {
    for (let last = 0; last < n; last++) {
      if (!(mask & (1 << last))) continue;
      const cur = dp[mask]![last]!;
      if (cur === Infinity) continue;
      for (let j = 0; j < n; j++) {
        if (mask & (1 << j)) continue;
        const next = mask | (1 << j);
        dp[next]![j] = Math.min(dp[next]![j]!, cur + dist[last]![j]!);
      }
    }
  }
  let ans = Infinity;
  for (let last = 0; last < n; last++) ans = Math.min(ans, dp[full]![last]!);
  return ans;
}