Bitmasking for Subset DP
What you'll learn: How to use bitmasks to represent subsets and efficiently solve dynamic programming problems involving small sets.
The Core Challenge
When solving DP problems that involve subsets of a collection (like selecting items, visiting cities, or choosing team members), representing every possible subset can be tricky. If we have n elements, there are 2ⁿ possible subsets. For small n (typically ≤ 20), we can use bitmasks to represent these subsets compactly.
What's a Bitmask?
A bitmask is simply an integer where each bit (0 or 1) indicates whether an element is included in the subset. For example, with 4 elements:
1011in binary (11 in decimal) means elements at positions 0, 1, and 3 are included (reading right-to-left)0100in binary (4 in decimal) means only element at position 2 is included
Analogy: Think of a light switch panel with n switches. Each switch being ON or OFF represents whether that item is in your subset.
Why Use This in DP?
Instead of storing DP states like dp[subset_array], you store dp[mask] where mask is an integer from 0 to 2ⁿ−1. This makes:
- State indexing instant (direct array access)
- Transition calculations efficient (bitwise operations)
- Memory usage predictable
Common operations:
- Check if element i is in mask:
mask & (1 << i) - Add element i:
mask | (1 << i) - Remove element i:
mask & ~(1 << i) - Iterate through all subsets: loop from 0 to 2ⁿ−1
Key Takeaway: Bitmasking transforms subset DP problems into efficient integer operations, allowing you to solve problems on small sets (up to ~20 elements) by representing each subset as a single integer and using bitwise operations for state transitions.