What would you like to Propose?
Add implementation(s) of dynamic programming on bitmasks, where DP state includes a bitmask representing a subset of elements already used/visited (e.g. dp[mask][i]). Useful for problems like TSP, optimal assignment, and subset-based counting where n is small (≤ ~20) and the order/combination of included elements matters. Covers core bit tricks (set/check/clear bit, iterate submasks) along with example problems.
Issue details
Bitmask DP represents a subset of elements as bits in an integer, where bit i being 1 means element i is included. The DP state dp[mask] (or dp[mask][i]) stores the best result for that subset, and transitions move from one mask to another by adding an element via mask | (1 << i). It's used when problems involve small sets (n ≤ ~20) and require tracking exactly which elements have been chosen, e.g., TSP, optimal assignment, and subset partitioning.
Additional Information
No response
What would you like to Propose?
Add implementation(s) of dynamic programming on bitmasks, where DP state includes a bitmask representing a subset of elements already used/visited (e.g. dp[mask][i]). Useful for problems like TSP, optimal assignment, and subset-based counting where n is small (≤ ~20) and the order/combination of included elements matters. Covers core bit tricks (set/check/clear bit, iterate submasks) along with example problems.
Issue details
Bitmask DP represents a subset of elements as bits in an integer, where bit i being 1 means element i is included. The DP state dp[mask] (or dp[mask][i]) stores the best result for that subset, and transitions move from one mask to another by adding an element via mask | (1 << i). It's used when problems involve small sets (n ≤ ~20) and require tracking exactly which elements have been chosen, e.g., TSP, optimal assignment, and subset partitioning.
Additional Information
No response