Subsets as integers
When a set is small, often up to around twenty elements, each subset can be encoded as the bits of an integer. A set bit means the element is present. This turns subsets into compact DP states. The traveling salesman problem and assignment problems use this pattern.
The traveling salesman state
Define dp at mask and i as the best cost of a path that visits exactly the cities in mask and currently sits at city i. Transitions extend the path:
- From state mask and i, move to an unvisited city j.
- The new mask adds bit j, and the cost adds the edge from i to j.
The final answer closes the tour by returning to the start once the mask includes every city.
Cost of the method
There is one state per subset and ending city, and each transition tries the remaining cities. This is far better than trying all orderings, though it grows quickly with the set size, which is why the set must stay small.
Key idea
Bitmask DP encodes a small set as integer bits so each subset is a state, letting problems like the traveling salesman be solved by transitions that flip one bit and extend the partial solution.