DP XII — Bitmask DP

Review boundary and corrected contracts

The assignment mask identifies used items and its popcount determines the next row. Partition-to-k uses positive numbers, 1 ≤ k ≤ n and a positive bucket target; zero targets otherwise divide by zero. The displayed continue retains every legal prefix transition when a large item overflows. A descending-break variant skips smaller candidates and needs a separate completeness argument; it is not the original implementation.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Treat a small n as a cue to estimate subset states and transitions, encode subsets as integers, and write the mask idioms without hesitating over bit syntax.

Series: LeetCode — From Basics to Production-Ready · Session 44 / 65 · Phase 2 · Dynamic programming

Why this session exists

Bitmask DP is useful when the relevant set is small enough for the actual state and transition count. Around twenty items is a common cue, not a universal limit or proof that an exponential algorithm is intended.

For n = 20 there are 1,048,576 subsets. A one-value-per-mask table and twenty candidate additions per mask have very different costs from a table with an extra endpoint axis, or a transition enumerating every submask. Estimate time and Python object storage before choosing the representation; a small cap can also accompany a simpler polynomial solution.

The second thing this session buys you is fluency. Bitmask problems are not conceptually harder than other DP — the state is a subset, the transitions add one element — but the syntax is unfamiliar enough that people lose minutes fumbling with shifts and ands. That fumbling is what actually costs you under a tight review, not the insight. So a chunk of this session is drilling the four or five idioms until they are automatic.

The third thing is knowing when not to use it. At n = 25 there are 33,554,432 subsets; scanning 25 candidates each gives 838,860,800 candidate checks before any application-specific work. These counts explain the risk without promising a machine-independent cutoff.

Blank-file warm-up

Five minutes, empty file, no notes. Write from memory:

1. for mask in range(1 << n) — the iteration over all subsets.
2. Test whether element i is in mask.
3. Add element i to mask, and remove it.
4. Count the set bits in mask, both with a builtin and with the n & (n-1) loop.

If any of these takes more than a few seconds to recall, that is the finding, and drilling them is more valuable than solving another problem today.

Pattern anatomy

The shape that summons this pattern: a set of at most about twenty items, where the answer depends on which subset you have already used, and order within the subset does or does not matter but membership definitely does.

The invariant: dp[mask] is the best value achievable having exactly the elements of mask already handled. Bit i of mask is 1 if element i has been used. Every subset gets exactly one integer, and every integer below 2^n is a valid subset — the correspondence is total, which is why the encoding works at all.

Here are the idioms. Learn them as vocabulary, not as puzzles:

n = 5
 
full = (1 << n) - 1          # 0b11111 — all elements present
empty = 0
 
# membership
if mask & (1 << i):          # is element i in the set?
    ...
 
# insert / remove / toggle
mask_with_i    = mask | (1 << i)
mask_without_i = mask & ~(1 << i)
mask_toggled   = mask ^ (1 << i)
 
# size of the subset
size = bin(mask).count("1")  # or mask.bit_count() on Python 3.10+
 
# lowest set bit, and clearing it
low   = mask & (-mask)       # isolates the lowest set bit as a power of two
mask2 = mask & (mask - 1)    # clears the lowest set bit
 
# iterate over every element present in mask
m = mask
while m:
    b = m & (-m)
    i = b.bit_length() - 1
    m ^= b
    ...

To enumerate every subset of an already chosen nonnegative mask, use (sub - 1) & mask. Subtracting one clears the lowest set bit and fills lower positions; AND removes positions outside the parent mask. Handle zero before the next update, or it cycles back to mask.

def submasks(mask):
    if mask < 0:
        raise ValueError("nonnegative mask required")
    sub = mask
    while True:
        yield sub
        if sub == 0:
            break
        sub = (sub - 1) & mask

This yields exactly 2^popcount(mask) values, including zero, in descending order. Enumerating submasks inside a loop over all n-bit masks instead costs 3^n visits: each position is absent, in the parent only, or in both. That is a different transition bound from the add-one-element skeleton below.

The bit operations tell us how to represent a subset; the DP still needs a reason to merge all histories that reach it. In the skeleton below, items are assigned to successive slots. The used subset determines the next slot through its size, so two assignment orders reaching that same subset have identical remaining choices. Keep only the cheaper history, then try each unused item in the next slot. If the next cost also depended on the last item visited, as in a travelling-salesman problem, the mask alone would not be enough — the endpoint would need its own state dimension. For this slot-assignment model, iterate masks in increasing order and push from each reachable mask to every mask that adds one more element:

def bitmask_dp(n, cost):
    INF = float("inf")
    dp = [INF] * (1 << n)
    dp[0] = 0
 
    for mask in range(1 << n):
        if dp[mask] == INF:
            continue                       # unreachable, skip
        k = bin(mask).count("1")           # how many placed so far
        for i in range(n):
            if mask & (1 << i):
                continue                   # already used
            nxt = mask | (1 << i)
            dp[nxt] = min(dp[nxt], dp[mask] + cost(k, i))
    return dp[(1 << n) - 1]

Increasing numeric order is a valid fill order, and this is worth understanding rather than accepting: adding a bit strictly increases the integer value, so mask | (1 << i) is always numerically greater than mask. Every dependency therefore sits at a lower index and is already final.

The bin(mask).count("1") inside the loop is O(n) per mask and turns an O(2^n · n) algorithm into O(2^n · n) with a fatter constant. If it matters, precompute a popcount array in a single pass: pc[m] = pc[m >> 1] + (m & 1). That recurrence is worth remembering on its own — it computes all popcounts up to 2^n in linear time in the number of masks.

The cue

You are looking at bitmask DP when the statement contains these tells:

1. n at most 16, 20, or 22. A cue to count subsets, not permission to ignore transition costs. At n = 20 the assignment skeleton scans about twenty million candidates; actual affordability depends on runtime and memory limits.
2. "Assign every item to some group" or "visit all nodes" or "partition into k subsets". These are all questions about which elements have been consumed, and consumption order is either irrelevant or captured by a second small dimension.
3. A permutation flavour with n small. Counting or optimising over orderings of at most twenty items — 20! has far more candidates than 2^20 × 20, because the DP collapses all orderings that use the same set into one state. That collapse is the entire win.
4. "Shortest path visiting all nodes" and anything else that smells of travelling-salesman. TSP is the archetype: state is (mask of visited, current node).
5. You reached for backtracking and the search tree is n!. If pruning is not obviously enough and n is small, the fix is to memoise on the set rather than the sequence.

Tell 3 is the conceptual heart. n! orderings but only 2^n sets means that if the future only depends on the set consumed rather than the order, you have collapsed a factorial into an exponential — an enormous saving that people often miss.

Guided solve

Partition to K Equal Sum Subsets — given an array nums and an integer k, decide whether the array can be split into k subsets with equal sums.

Start with the cheap rejections, because they cost two lines and eliminate most invalid inputs:

• If sum(nums) is not divisible by k, return False immediately.
• Let target = sum(nums) // k. If any single element exceeds target, return False — that element can never fit anywhere.

Now the framing. The naive approach is backtracking: try to fill bucket one, then bucket two, and so on. It works with aggressive pruning but the search tree is large and the pruning rules are fiddly to get right under pressure.

The bitmask reframing is cleaner. Do not track k separate buckets. Instead, walk through the elements in one long sequence, filling one bucket at a time, and let the running sum modulo target tell you where the bucket boundaries fall. The key realisation: if mask tells you which elements are used, then sum(mask) is determined, so the amount currently in the partially-filled bucket is sum(mask) % target — you do not need to store it. The mask alone is a sufficient state.

def canPartitionKSubsets(nums, k):
    if not nums or not 1 <= k <= len(nums) or any(x <= 0 for x in nums):
        raise ValueError("nonempty positive values and 1 <= k <= n required")
    total = sum(nums)
    if total % k:
        return False
    target = total // k
    if max(nums) > target:
        return False
 
    n = len(nums)
    nums.sort(reverse=True)                 # mutates input; fixes a deterministic bit order
 
    full = (1 << n) - 1
    # subset_sum[mask] = sum of the chosen elements
    subset_sum = [0] * (1 << n)
    for mask in range(1, 1 << n):
        low = mask & (-mask)
        i = low.bit_length() - 1
        subset_sum[mask] = subset_sum[mask ^ low] + nums[i]
 
    dp = [False] * (1 << n)                 # dp[mask] = mask is a valid prefix state
    dp[0] = True
 
    for mask in range(1 << n):
        if not dp[mask]:
            continue
        used = subset_sum[mask] % target    # how full the current bucket is
        for i in range(n):
            if mask & (1 << i):
                continue
            if used + nums[i] > target:
                continue                    # would overflow the current bucket
            dp[mask | (1 << i)] = True
    return dp[full]

Two things carry correctness. For a reachable mask, completed buckets each contribute exactly target, so subset_sum[mask] % target is the next bucket's fill level. Adding an item is legal only if it does not exceed target; reaching target resets the remainder to zero and starts the next bucket. An underfull bucket can accept more items but cannot be abandoned. At full mask the total is k·target, so there are exactly k nonempty buckets (positivity is essential). Conversely, concatenating any valid partition's buckets produces a legal sequence of these transitions.

Sorting is not a pruning optimisation in this exhaustive DP. It relabels item bits but leaves the reachable-subset graph and candidate checks unchanged: each reachable mask still scans every index. The displayed descending order uses continue on overflow because a later smaller item may fit; this preserves the stated reachable-prefix invariant. The original code already did this correctly. Unlike a depth-first search, it neither stops at the first solution nor skips all remaining candidates. The sort mutates nums; pass a copy if callers need its order preserved.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Shortest Path Visiting All Nodes — the state is (mask, current_node), so the table has 2^n × n entries. This is a BFS over that state space rather than a fill-order DP, because edge weights are uniform. Think about what the start states are — there is more than one.

If that lands early, attempt Number of Ways to Wear Different Hats or Maximum Students Taking Exam. The latter uses a mask per row rather than a mask over all elements, which is a genuinely different flavour worth seeing.

Common failure modes

Operator precedence on the membership test. In Python, shifts bind tighter than bitwise &, and & binds tighter than comparisons. Thus mask & 1 << i == 0 already parses as (mask & (1 << i)) == 0. Parentheses are useful for readability, not a repair to this expression.

Iterating masks in the wrong direction. These add-one-element transitions require dependencies to be processed first. Increasing masks works for either push or pull; mixing styles is not inherently incorrect, but every read and write still needs a dependency argument.

Recomputing state summaries inside the candidate loop. An O(n) popcount once per mask leaves the O(n·2^n) bound unchanged here. Recomputing it for each of n candidates can add another factor of n. Precompute sums when needed, and measure constants rather than promising a timeout.

Not skipping unreachable states. Without the if dp[mask] is unreachable: continue guard you do n units of work on states that can never contribute. On a million masks that is twenty million wasted operations for nothing.

Assuming n is small when it is the array length of something else. Read carefully which quantity the constraint bounds. nums.length <= 20 is your green light; nums[i] <= 20 is not.

Myth: Bitmask DP is exponential, so it is a brute-force approach dressed up in bit tricks rather than real dynamic programming.

Why: It is exponential in n but it is emphatically not brute force, and the gap is enormous. Brute force over orderings of n items is n! — for n = 20 that is about 2.4 quintillion. Bitmask DP is 2^n, about a million for the same n. The saving comes from the defining DP property: all orderings that consume the same set of elements collapse into one state, because the future cost depends only on what remains, not on the order in which the past was consumed. That collapse from n! to 2^n is exactly what memoisation buys, and it is the same argument that makes any DP better than the recursion it replaces.

Steps 1: Because each of n elements is either used or unused, the set of used elements is one of exactly 2^n possibilities.

Steps 2: Because an integer's binary representation is itself a sequence of n independent bits, integers below 2^n are in exact one-to-one correspondence with those subsets.

Steps 3: Because array indexing by that integer is O(1), the subset becomes a directly addressable DP key with no hashing overhead.

Steps 4: Because adding an element strictly increases the integer value, iterating masks in increasing numeric order guarantees every dependency is already final.

Steps 5: Because there are 2^n states and each considers at most n additions, total work is O(2^n · n).

Steps 6: Increasing n to n+1 multiplies the n·2^n candidate bound by 2(n+1)/n. This is an operation-count prediction, not a measured runtime ratio; reachability, allocations and machine limits affect elapsed time.

Picture: A panel of n light switches. Every possible configuration of the panel is one number, read off as binary. Your DP table has one slot per configuration, and a transition is flipping exactly one switch from off to on — which always makes the number larger, so you can just sweep the slots left to right.

Trigger: Fires the instant you read a constraint of n at most 20 on a problem about choosing, assigning, or ordering items.

Name: Bitmask DP over subsets

Gain: A sufficient state and valid recurrence give predictable O(2^n · n) candidate work; correctness still requires the state proof, not just a bitmask encoding

Cost: Always pays the full 2^n even when the real search space is tiny; memory is 2^n entries which is fixed regardless of input structure

Name: Backtracking with pruning

Gain: Often dramatically faster on real inputs because good pruning kills most branches early; memory is O(n) recursion depth

Cost: Worst case is still factorial; performance depends entirely on the quality of your pruning rules, which are problem-specific and easy to get subtly wrong

Pick: Choose subset DP when the state is sufficient and its full table and transitions fit the budget. Choose backtracking when valid pruning reduces the explored tree enough; for descending candidates a later smaller item can fit after an overflow, so continue preserves every legal prefix transition. A first-overflow break follows directly from monotonicity only in ascending order; other pruning needs its own proof.

Complexity

Time: O(2^n · n) for the assignment and partition skeletons, assuming O(1) costs and bounded-size masks/values. At n = 20 that is about 20.97 million candidate checks, not a promise of seconds in Python or milliseconds in C++.

Space: O(2^n) table entries, plus O(2^n) subset sums for partition. Python lists store references and integer/float objects add storage, so count objects as well as entries. Whether a million or sixteen million entries fit is an environment limit, not a theorem.

The dense TSP variant is O(2^n · n²): a visited mask and endpoint, with up to n transitions. The loose n²·2^n count is 589,824 at n = 12 and 419,430,400 at n = 20 (many mask/endpoint pairs are invalid). Count the actual reachable transitions and memory before choosing it; the assignment bound does not transfer unchanged.

Self-check (answer follows each question).

Q: What does the constraint n <= 20 tell you, and why that specific number?

A: It suggests considering a subset algorithm: 2^20 is 1,048,576 and 20·2^20 is 20,971,520 candidate checks for this skeleton. It neither forces that solution nor guarantees it will fit; extra state dimensions, transition work and object storage matter.

Q: Write the expressions to test, set, and clear bit i of mask.

A: Test: mask & (1 << i). Set: mask | (1 << i). Clear: mask & ~(1 << i). Python shifts bind tighter than bitwise AND, which binds tighter than comparisons. Parentheses make the grouping explicit; they do not repair a precedence bug here.

Q: Why is iterating masks in increasing numeric order a valid fill order for forward transitions?

A: Setting a previously-unset bit strictly increases the integer, so every mask you push to is numerically larger than the mask you push from. All dependencies therefore sit at strictly lower indices and are already final.

Q: In Partition to K Equal Sum Subsets, why is the mask alone a sufficient state — why not also store how full the current bucket is?

A: Because the mask determines the sum of chosen elements, and every completed bucket contributed exactly target. So subset_sum[mask] % target recovers the current bucket's fill level exactly, making it redundant information.

Q: What does mask & (mask - 1) compute, and what is one use for it?

A: It clears the lowest set bit. Repeatedly applying it counts set bits in time proportional to the number of ones rather than the number of bit positions, and it is the standard way to iterate over set members.

Q: Bitmask DP is 2^n while brute force over orderings is n!. Where exactly does the saving come from?

A: All orderings that consume the same set of elements are merged into a single state, because the remaining cost depends only on what is left rather than on the order the past was consumed in. That is the optimal-substructure collapse, and for n = 20 it takes 2.4 quintillion down to about a million.

Stretch: true

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Add a separate queue entry for the bit idioms themselves, not just for the problems. Fluency with 1 << i and mask & (-mask) decays independently of whether you remember how Partition to K Equal Sum Subsets works.

• A small n suggests checking subset DP; it is not proof of intent or affordability. Count states, transitions and bytes.

• A subset is an integer; bit i set means element i is used. The correspondence is exact and directly addressable.

• Iterate masks in increasing numeric order — adding a bit always increases the value, so dependencies are always already final.

• Precompute subset sums with the lowest-set-bit recurrence. Compute popcount once per mask, not once per candidate; precomputation is optional for the displayed bound.

• The win over brute force is collapsing n! orderings into 2^n sets, because the future depends on what remains, not on order consumed.

• TSP-shaped problems need state (mask, last node), which costs O(2^n · n^2) — check that bound before committing.

Corrective source notes

• Enumerating submasks of a bitmask - Algorithms for Competitive Programming — A mask encodes a subset by bit membership; this does not eliminate exponential subset counts. Checked 2026-10-07.

• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.

• Python 3.14 reference — Operator precedence — Python shifts bind tighter than bitwise AND, and bitwise AND binds tighter than comparisons. Checked 2026-10-07.

• Python 3.14 integer methods — bit_count counts ones in the absolute value and was added in Python 3.10. Operator precedence was freshly rechecked in the 3.14 reference on 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.