Bitmask Coding Problems: 29 Questions with Solutions
29 bitmask coding problems — 8 medium · 21 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 7-day plan.
- Problems: 29
- By difficulty: 8 medium · 21 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
A bitmask uses the bits of one integer as a set of small items: bit i is on when item i is chosen, used or visited. With at most 15 or 20 items every subset is a number below 2ⁿ, so it can index an array, and dynamic programming over subsets — which tasks are done, which nodes have been visited, which primes a product already contains — becomes a table of 2ⁿ entries. The problems here practise that table, the bit operations that move from one subset to the next, and spotting the small bound that makes it affordable.
How bitmask works, step by step
nums = [3, 5, 1]; which subsets sum to 6?- Each subset of [3, 5, 1] is a 3-bit mask: bit j, counted from the right, set means nums[j] is in, and mask 000 is the empty set with sum 0. Clearing a mask's lowest set bit, mask & (mask − 1), gives a smaller mask, which is already done.
- mask 001 = {3}: its lowest set bit is bit 0 (nums[0] = 3), and without it the mask is 000, the empty set, already known to sum to 0. So sum[001] = 0 + 3 = 3. One addition per mask, never a loop over the bits.
- mask 010 = {5}: its lowest set bit is bit 1 (nums[1] = 5), and without it the mask is 000, the empty set, already known to sum to 0. So sum[010] = 0 + 5 = 5. A single-bit mask always comes from 000.
- mask 011 = {3, 5}: its lowest set bit is bit 0 (nums[0] = 3), and without it the mask is 010, {5}, already known to sum to 5. So sum[011] = 5 + 3 = 8.
- mask 100 = {1}: its lowest set bit is bit 2 (nums[2] = 1), and without it the mask is 000, the empty set, already known to sum to 0. So sum[100] = 0 + 1 = 1. Going through the masks in increasing order is what makes this safe: mask & (mask − 1) is always smaller, so it is always done.
- mask 101 = {3, 1}: its lowest set bit is bit 0 (nums[0] = 3), and without it the mask is 100, {1}, already known to sum to 1. So sum[101] = 1 + 3 = 4.
- mask 110 = {5, 1}: its lowest set bit is bit 1 (nums[1] = 5), and without it the mask is 100, {1}, already known to sum to 1. So sum[110] = 1 + 5 = 6.
- mask 111 = {3, 5, 1}: its lowest set bit is bit 0 (nums[0] = 3), and without it the mask is 110, {5, 1}, already known to sum to 6. So sum[111] = 6 + 3 = 9. The last mask, the whole set, reuses 110 like every other.
- All 8 subset sums came from one addition each: O(2ⁿ), not O(n·2ⁿ) for re-adding every subset. Any question about subsets is now a lookup: 110 = {5, 1} is the only one summing to 6.
Bitmask study plan
10 of the 29 Bitmask problems (7 medium and 3 hard) over 7 days, about 6 h 50 min in all — the pattern first, then easiest to hardest. After that, the other 19 in the full list below are practice at your own pace. Then move on to Number Theory.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.
Day 2
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Beautiful Arrangement Medium
- Special Permutations Medium
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Partition to K Equal Sum Subsets Medium
- Matchsticks to Square Medium
Day 5
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
Day 6
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Bitmask: the essentials
When to reach for it
One dimension is tiny — up to 20 tasks, nodes or slots, the ten primes below 30, a grid five cells wide — and what matters is which items are used, not their order: "assign every task", "visit every node". 2²⁰ is about a million states; much beyond 20 items, look elsewhere.
The pattern
Let dp[mask] be the best result using exactly the items in mask. A transition adds an item (mask | (1 << i)) or a submask; increasing mask order works, as setting a bit makes the number larger. A walk through every node must also know where it is: the state is (mask, last item). Bit basics are on Bit Manipulation.
def min_sessions(tasks, limit): # fewest sessions of at most limit hours
n = len(tasks)
best = [(n + 1, 0)] * (1 << n) # best[mask]: (sessions, hours in the last one)
best[0] = (1, 0)
for mask in range(1 << n):
s, used = best[mask]
for i, t in enumerate(tasks):
if not mask & (1 << i): # task i is not done yet
nxt = (s, used + t) if used + t <= limit else (s + 1, t)
best[mask | (1 << i)] = min(best[mask | (1 << i)], nxt)
return best[-1][0]
Cost
O(2ⁿ × n) time and O(2ⁿ) space when each transition adds one item. Looping over every submask of every mask is O(3ⁿ), about 1.4 × 10⁷ for n = 15. A last item in the state multiplies both by n.
Common mistakes
- A state missing what the future needs: a walk through every node needs the current node too.
- Starting entries at 0 in a minimisation, so impossible subsets look free; start at infinity.
- The submask loop
sub = (sub - 1) & maskends at 0: handle the empty submask apart, or it is skipped or never stops. - One bit per slot when a slot holds two items; use two bits, or base 3.
Start with
- Minimum Number of Work Sessions to Finish the Tasks: a pair of numbers per subset.
- Shortest Path Visiting All Nodes: breadth-first search over (node, visited set).
- Count the Number of Square-Free Subsets: a mask over the ten primes below 30.
All bitmask problems
Medium (8)
- Can I Win Math, Dynamic Programming, Bit Manipulation
- Matchsticks to Square Array, Backtracking, Dynamic Programming
- Partition to K Equal Sum Subsets Dynamic Programming, Backtracking
- Fair Distribution of Cookies Dynamic Programming, Backtracking, Bit Manipulation
- Maximum Compatibility Score Sum Dynamic Programming, Backtracking, Bit Manipulation
- Special Permutations Array, Dynamic Programming, Bit Manipulation
- Beautiful Arrangement Dynamic Programming, Backtracking, Bit Manipulation
- Minimum Number of Work Sessions to Finish the Tasks Array, Dynamic Programming, Bit Manipulation
Hard (21)
- Select Cells in Grid With Maximum Score Array, Dynamic Programming, Bit Manipulation
- Maximize the Number of Partitions After Operations String, Dynamic Programming, Bit Manipulation
- Maximum Number of Groups Getting Fresh Donuts Array, Dynamic Programming, Bit Manipulation
- Minimum Cost to Connect Two Groups of Points Array, Dynamic Programming, Bit Manipulation
- Number of Squareful Arrays Array, Math, Backtracking
- Closest Subsequence Sum Array, Two Pointers, Sorting
- Stickers to Spell Word String, Dynamic Programming, Backtracking
- Distribute Repeating Integers Array, Backtracking, Dynamic Programming
- Partition Array Into Two Arrays to Minimize Sum Difference Array, Binary Search, Bit Manipulation
- Maximize Score After N Operations Math, Dynamic Programming, Number Theory
- Parallel Courses II Dynamic Programming, Bit Manipulation, Graph
- Number of Ways to Wear Different Hats to Each Other Array, Dynamic Programming, Bit Manipulation
- Maximum Students Taking Exam Dynamic Programming, Bit Manipulation, Matrix
- Minimum XOR Sum of Two Arrays Array, Dynamic Programming, Bit Manipulation
- Maximum Score Words Formed by Letters Array, String, Backtracking
- The Number of Good Subsets Array, Math, Dynamic Programming
- Painting a Grid With Three Different Colors Dynamic Programming
- Minimum Incompatibility Array, Dynamic Programming, Bit Manipulation
- Shortest Path Visiting All Nodes Bit Manipulation, Breadth-First Search, Graph
- Count the Number of Square-Free Subsets Bit Manipulation, Dynamic Programming, Math
- Maximum AND Sum of Array Bit Manipulation, Dynamic Programming
Companies that ask bitmask problems
Next topic: Number Theory