Subsets as integers
When a problem ranges over subsets of a small set, you can encode each subset as an integer whose bits mark membership. With twenty items you have about a million subsets, a count small enough to visit. Bitmask dynamic programming stores one answer per subset and builds larger subsets from smaller ones.
The classic example
Consider assigning workers to tasks for minimum total cost. Let the mask record which tasks are already assigned. The number of set bits tells you how many workers have been placed, so it identifies the worker about to be assigned next.
- The state is the mask of used tasks.
- For each state you try every unused task for the next worker.
- You combine the cost of that choice with the best answer for the smaller mask.
Reading and setting bits
- Test whether item k is in a mask by checking bit k.
- Add item k by setting bit k.
- Iterate over set bits to enumerate members.
Because every subset is processed once and each transition scans the items, the approach is exponential in the item count but practical for small sets.
Key idea
Encode each subset as the bits of an integer and fill a table from smaller masks to larger ones, which tames problems over small sets that would otherwise be intractable.