Bitmask DP: subsets as integers

When n is small — roughly n ≤ 20 — and the state you need is "which subset of items have I used," the move is to pack that subset into the bits of an integer. A set over n elements becomes a number in [0, 2ⁿ), and dp[mask] is indexed by that number. Subset DP that would be unstatable becomes a flat array.

The canonical example is the traveling salesman. Let dp[mask][i] be the shortest path that visits exactly the set of cities in mask and currently sits at city i. You extend by moving to an unvisited city j:

bool has   = mask & (1 << i);      // is element i in the set?
int  added = mask | (1 << i);      // add element i
int  gone  = mask & ~(1 << i);     // remove element i

// iterate every submask of mask, in O(3^n) total over all masks:
for (int s = mask; s; s = (s - 1) & mask) { /* s ranges over submasks */ }

Mind the complexity wall. TSP is O(2ⁿ · n²): with n = 20 that is 2²⁰ · 400 ≈ 4 × 10⁸ — right at the edge of a time limit, which is exactly why bitmask DP lives at n ≤ 20 and not beyond. The state count 2ⁿ is the whole budget; spend it knowingly.

The submask-enumeration loop is the other half of the toolkit: s = (s − 1) & mask walks every subset of a mask, and summed over all masks it is O(3ⁿ), not O(4ⁿ) — because each element is in/out/neither. That is the engine behind set-partition and assignment DPs, where you split a set into pieces and recurse on the complement.