Counting and Bitmask DP

What is this?

Two of these problems have a transition that sums a whole range of earlier states — which is correct, and too slow. Both collapse to a sliding window by writing the recurrence twice and subtracting. The other three are about state: a ± assignment problem that turns out to be subset sum, and two searches whose state is "what still needs covering" rather than an index.

flowchart TD A["Counting and Bitmask"] --> B["summed transition"] A --> C["state = what's left"] B --> B1["K Inverse Pairs
dp[n][k] = Σ dp[n−1][k−j]"] B1 --> B2["subtract adjacent k → 3 terms"] B --> B3["New 21 Game
dp[i] = mean of the last W states"] B3 --> B4["running window sum"] C --> C1["Target Sum → subset sum"] C --> C2["Stickers → remaining letters"] C --> C3["Word Break II → remaining suffix"]

💡 Fun fact: Target Sum asks how many ways to put + or − in front of each number to reach a target, and looks like 2ⁿ enumeration. Let P be the numbers you make positive and N the rest. Then P − N = target and P + N = total, so P = (total + target) / 2 — a fixed number. The question collapses to "how many subsets sum to P", an ordinary 0/1 knapsack count. As a bonus, if total + target is odd or |target| > total the answer is instantly 0. Turning a signed-assignment problem into a subset sum by adding the two equations is a move worth keeping.

🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: if a transition sums many earlier states, write it for k and for k−1 and subtract. Nearly every term cancels, and an entire dimension of work disappears.

1. Collapse the sum

The natural recurrence for K Inverse Pairs — inserting the n-th element can create 0 to n−1 new inversions — is a range sum:

dp[n][k] = dp[n-1][k] + dp[n-1][k-1] + … + dp[n-1][k-n+1]

Write the same line for k−1 and subtract. Everything cancels except the two edges:

dp[n][k] = dp[n][k-1] + dp[n-1][k] - dp[n-1][k-n]

O(n²k) becomes O(nk) and the code shrinks. Two details bite: dp[n-1][k-n] only exists when k ≥ n, and the subtraction can go negative before the modulo, so normalise after every step.

2. The same move, as a window

New 21 Game draws uniformly from 1 … maxPts while below k, and asks for the probability of finishing at or below n. Each state is the mean of the previous maxPts states — the same summed transition, so the same fix:

dp[0], window, ans = 1.0, 1.0, 0.0
for i in range(1, n + 1):
    dp[i] = window / maxPts
    if i < k: window += dp[i]                      # still drawing
    else:     ans   += dp[i]                       # stopped here, and it counts
    if 0 <= i - maxPts < k: window -= dp[i-maxPts]  # slide the window

The guard is exact: a state leaves the window only if it was ever in it, which requires i - maxPts < k. The early exit if k == 0 or n >= k + maxPts - 1: return 1.0 handles the case where stopping below n is certain — and skipping it leaves an array of size n that is never needed.

3. State that is "what remains"

Stickers to Spell Word memoises on the sorted remaining letters, not on an index:

@lru_cache(None)
def go(rem):
    if not rem: return 0
    first = rem[0]                                 # must be covered by SOME sticker
    for c in counts:
        if c[first] == 0: continue                 # ← the pruning that makes it feasible
        ...

Requiring every candidate sticker to contain rem[0] prunes enormously and costs nothing in correctness — that letter has to come from somewhere, so trying stickers that cannot supply it only re-derives orderings already explored. Sorting the remainder is what makes two equivalent states hash to the same key.

Word Break II is the same idea over suffixes, memoised on the start index, returning the list of sentences rather than a count. Memoising is what keeps a string like "aaaaaaaa" with dictionary ["a","aa","aaa"] from re-deriving the same suffix repeatedly — though the output can still be exponential, which is a property of the question.

4. A 30-second worked example (Target Sum)

nums = [1,1,1,1,1], target = 3

total = 5,  target = 3
total + target = 8, even  ✓        P = 8 / 2 = 4

so: how many subsets of [1,1,1,1,1] sum to 4?
    choose 4 of the 5 ones → C(5,4) = 5

answer: 5      (and indeed +1+1+1+1−1 and its four rearrangements)

The check that saves the most time is the parity one. With target = 2, total + target = 7 is odd, no subset sum exists, and the answer is 0 before a table is allocated — a fact no amount of enumeration would have discovered as quickly.

5. Where you'll actually meet this

Risk and gaming systems. New 21 Game is a bounded random walk, which is how ruin probabilities are actually computed.
Inventory and fulfilment. Stickers is "cover this order from these packs, using as few as possible".
Search and autocomplete. Word Break II is segmentation for languages written without spaces.
Ranking and sorting analysis. Inversion counts measure how far a ranking is from a reference.
Budget and portfolio allocation. Subset-sum counting underlies "how many ways can this be funded exactly".

6. Problems in this chapter

▶ K Inverse Pairs Array

Count arrays with exactly k inverse pairs. The summed transition collapses to three terms by differencing adjacent states.
Pattern: counting DP with a collapsed range sum. Target: O(nk) time, O(k) space.

▶ New 21 Game

Probability of stopping at or below n. Each state is the mean of a fixed window of earlier states, maintained as a running sum.
Pattern: probability DP with a sliding window. Target: O(n) time, O(n) space.

▶ Target Sum

Count ± assignments reaching a target. Solve for the positive subset's sum and count subsets that reach it.
Pattern: subset-sum counting. Target: O(n · sum) time, O(sum) space.

▶ Stickers to Spell Word

Fewest stickers spelling a target. Memoise on the sorted remaining letters and only try stickers covering the first one.
Pattern: memoised search over remaining state. Target: exponential worst case, fast with the pruning.

▶ Word Break II

Every sentence formable from the dictionary. Memoise on the start index and return the list of completions of each suffix.
Pattern: memoised backtracking. Target: output-bound.

7. Common pitfalls 🚫

Leaving the summed transition in place. It passes the samples and times out on the real constraints.
Reading dp[n-1][k-n] when k < n. That term does not exist and must be guarded.
Taking a modulo of a negative. Normalise after every subtraction.
Sliding the probability window unconditionally. A state only leaves if it ever entered — i - maxPts < k.
Missing the parity check in Target Sum, which decides many inputs instantly.
Memoising stickers on an unsorted remainder, so equivalent states never share a cache entry.
Dropping the first-letter pruning, which is the difference between fast and hopeless.

8. Key takeaways

A summed transition is a signal, not a solution. Difference adjacent states and it collapses.
A sliding window is the same trick wearing a probability hat.
Add the two equations. P − N = target with P + N = total turns signs into a subset sum.
State can be "what is left" rather than "how far you have come".
Canonicalise the memo key — sort the remainder, or equivalent states never merge.
A forced-coverage pruning is free correctness: the first uncovered letter must come from somewhere.
Why interviewers like it: the naive recurrence is easy and quadratic, so the optimisation is precisely the thing being measured.

Order: K Inverse Pairs Array → New 21 Game → Target Sum → Stickers to Spell Word → Word Break II.

Word Break II

Core idea: Word Break I only asked can the string be split into dictionary words. Word Break II asks for every way to do it — return all sentences you can form by inserting spaces so each piece is a valid word. The clean attack is recursion over suffixes: define solve(start) = the list of all sentences that segment s[start:]. For every end where s[start:end] is a dictionary word, recurse on solve(end) to get all sentences for the remaining suffix, then prefix the word onto each of them. The base case solve(len(s)) returns [""] — one empty sentence, meaning "the suffix is empty, segmented trivially." The number of valid sentences is potentially exponential, so you can't beat that in the worst case — but memoizing solve by start means each distinct suffix is solved once and its full list of sentences is reused everywhere that suffix appears. Spotting that shared suffixes shouldn't be recomputed is the senior move.

The problem, rephrased

You're handed a string with no spaces — a run-together phrase like applepenapple — and a dictionary of allowed words. You want to recover every possible sentence: every way to slice the string so that, reading left to right, each slice is a word in the dictionary. Unlike the yes/no feasibility version, here a single input can have many valid readings ("catsanddog" reads as both "cats and dog" and "cat sand dog"), and you must return all of them.

Formally: given a string s and a list wordDict of words, add spaces in s to construct a sentence where every word is in wordDict, and return all such sentences in any order. The same dictionary word may be reused any number of times.

This is LeetCode 140 — Word Break II.

Input	Means	Output
`s = "catsanddog"`, `dict = ["cat","cats","and","sand","dog"]`	two readings of the prefix `cats`/`cat`	`["cats and dog", "cat sand dog"]`
`s = "pineapplepenapple"`, `dict = ["apple","pen","applepen","pine","pineapple"]`	`pine`/`pineapple` branch, etc.	`["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]`
`s = "catsandog"`, `dict = ["cats","dog","sand","and","cat"]`	no way to consume the tail `og`	`[]`

The whole story is the suffix: once you commit a word as the prefix, what remains is a smaller instance of the same problem on s[end:] — and that suffix may be reachable from several different prefixes.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Advanced