Algorithms and Data Structures · Senior · Question 26 of 75
What does bitmask DP use as its state?
- ✓Correct answer: An integer whose bits mark the elements used
- 2A sorted array of the elements chosen so far
- 3A string describing the path taken so far
Explanation
With n up to about 20, subsets fit in an integer: mask | (1 << i) adds element i, mask & (1 << i) checks it. States like dp[mask][last] solve TSP and assignment problems in O(2ⁿ × n²).