Bitmask DP represents a set of chosen or visited items as bits in an integer.
It is useful when the state must remember which items from a small collection have already been used.
Core Idea
If there are n items, a mask from 0 to 2 ** n - 1 can represent any subset. Bit i is 1 when item i is included.
The number of masks grows exponentially, so this technique is usually for relatively small n.
Python Example
def contains(mask, i):
return (mask & (1 << i)) != 0
def add_item(mask, i):
return mask | (1 << i)These operations test and add items using bit positions.
Common Confusions
Bitmask DP is not faster because bits are magical. It is useful because it gives a compact way to store subset state.
The number of states can still be huge. 2 ** 20 is already more than one million masks.
When To Use It
Use bitmask DP for subset selection, visiting all nodes in a small graph, assignment problems, and traveling-salesman-like states.