Deep Dive: Bitmask DP

Learning Outcome

Build interview depth for Bitmask DP.

Pattern Recognition

Intuition

A bitmask compactly represents a chosen subset.

Exact Practice Question Names

• Parallel Courses II
• Traveling Salesman Pattern

Interview Approach

1. Start with the base family.
2. Identify the new state or constraint.
3. Show why the simpler approach fails.
4. Add the smallest extra state needed.
5. Dry-run a follow-up example.

Pseudocode

base_pattern_state
extra_state_from_followup
process in valid order
relax/update answer
return final state
  

Sample Dry Run

Use one small Bitmask DP sample and explicitly track the extra state introduced by the follow-up.

Edge Cases

• Disconnected/unreachable state
• Cycles or repeated states
• Large constraints
• Tie-breaking

Common Mistakes

• Forcing the base template without adding required state
• Not proving why revisits are safe or unsafe
• Missing cycle handling

Complexity

Java, C++ and Python Notes

• Java: prefer explicit classes and clear helper methods over clever one-liners.
• C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
• Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

• Name the pattern before coding.
• State the invariant or DP state in one sentence.
• Dry-run the smallest non-trivial example.
• Close with time and space complexity.