What is bitmask dynamic programming?

Question presented to candidate: "What is bitmask dynamic programming? Explain when you would reach for it, describe the state for a classic problem such as assigning n workers to n jobs or the travelling salesman problem, and show me what it looks like in Python."

What a strong answer should cover:

• A bitmask is an integer used as a set (bit i = element i); with n elements there are 2ⁿ masks, so it fits when n is small (about 20 or less).
• The condition that makes it valid: the future depends only on which elements are used, not the order — replacing n! orders with 2ⁿ subsets.
• Concrete states: dp[mask] for assignment (next worker = popcount), dp[mask][last] for TSP (Held–Karp, O(n² · 2ⁿ) time, O(n · 2ⁿ) space).
• Fill order by increasing mask, the core bit operations, and submask enumeration with its 3ⁿ total cost.
• Python details: unbounded int masks (no overflow), operator precedence (mask >> i & 1 is fine), int.bit_count() (3.10+) or bin(m).count('1'), and that Python loops over 2ⁿ · n states are slow, so keep n ≤ about 16–18.

Code / implementation expected: Optional — a short dp[mask] assignment or dp[mask][last] TSP in Python is a strong way to show you mean it.