Bitmask DP

When "which subset of items has been visited/used" is part of the state, encode the subset as a bitmask integer: state = (position, mask). Only feasible when n is small (roughly ≤ 20), since 2ⁿ masks must be enumerable.

Sub-patterns

• A — Assignment-Style Bitmask DP. Assign items to slots, tracking which have been used as a bitmask.
• B — Traveling-Salesman-Style DP. State = (current node, visited-set bitmask).

Practice set (4)

• Medium — Partition to K Equal Sum Subsets
• Hard — Shortest Path Visiting All Nodes, Minimum Cost to Connect Two Groups of Points, Maximum Students Taking Exam