Bitmask DP
A bitmask encodes which elements are used; classic for TSP on small n.
Decision · step 11 of 15Bitmask DP: Four cities, eight subsets that contain the start
Set 1111 = {A, B, C, D}, ending at B. The path arrived from the set without B, 1101 = {A, C, D}, which is one bit off and therefore a smaller number, so its row is already filled. Try every end of that row: via C: 50 + 35 = 85; via D: 45 + 25 = 70. The cheapest is via D, 70.
What you will see
Rows indexed by masks shown as binary; transitions flip one bit.
Cost
| Best | O(2^n * n) |
|---|---|
| Average | O(2^n * n) |
| Worst | O(2^n * n) |
| Space | O(2^n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Table cells announce their state and value; each step announces which cells were read and the value written.
Reduced motion: Dependency arrows appear statically and the cell value crossfades.