When do overlapping subproblems make a divide-and-conquer split the wrong tool?

## What independence actually means Two conditions hide under the word *independent*: 1. **No result dependency.** No subproblem needs another subproblem's answer as input. If the right half cannot be started until the left half is finished, you have a sequential chain, not two branches. 2. **No repeated instances.** The recursion should not arrive at the same subproblem instance again and again through different paths. This is the condition that fails in dynamic-programming problems, and it is the one people miss. Divide and conquer assumes both. When the second fails, the algorithm is still *correct* — it just does an absurd amount of duplicated work. ## The shape of overlap Overlap almost always appears for a structural reason: **the split point is itself a decision**. In a classic divide-and-conquer decomposition you split at a fixed place — the midpoint of a range, the median coordinate of a point set — and each branch owns a disjoint piece. Nothing can recur, because no other call ever produces those same boundaries. Now suppose the best split is not known in advance, so the algorithm tries every possible split and takes the best result. Every choice of split produces two subranges, and those subranges are shared with the subranges produced by *other* choices, at every level of the recursion. The recursion tree becomes exponentially wide while the set of distinct arguments — pairs of boundaries — is only quadratic. ``` best(0, 8) tries k = 1..7 -> best(0, 3) and best(3, 8) -> best(0, 5) and best(5, 8) both of these recompute best(0, 3) inside ``` That is the signature: distinct arguments are polynomially many, calls are exponentially many, and the ratio between them is exactly the work memoization saves. ## The check you can run before writing code - **Do the branches partition the input?** Halves of a range, disjoint sets of points, the two subtrees of a node — those are partitions, and partitions cannot overlap. Two branches that both read the same middle region, or that are parameterised by a *choice* rather than by a fixed boundary, are suspicious. - **Count distinct subproblems.** Enumerate the argument tuples the recursion can produce. If a single index gives `n` states, a pair of boundaries gives `O(n²)`, a boundary plus a remaining budget gives `O(n * B)`. Compare that count with how many calls the recursion actually makes. - **Draw two levels of the tree.** Repeated argument tuples appearing in different branches is direct evidence, and it takes thirty seconds. ## What to do about it Remember the answers. Add a store keyed by the subproblem's arguments; on entry, return the stored answer if present; on exit, store what you computed. The recursion's structure does not change at all — the same divide, the same conquer, the same combine — but the analysis does. Instead of a recurrence over input sizes, the cost becomes: **(number of distinct subproblems) × (work done per subproblem, excluding recursive calls)** For the boundary-pair example that is `O(n²)` states times `O(n)` split choices each, so `O(n³)` — a wholly different, and finite, universe from the exponential version. The bottom-up variant fills the same table in an order that guarantees dependencies are ready before they are needed, avoiding recursion depth entirely. ## What this does *not* mean It does not mean the recursion was a bad idea. The recursive decomposition is how you *found* the recurrence in the first place, and memoizing it is a mechanical step afterwards. It also does not mean overlap is always fatal to the divide-and-conquer framing: if the repeated subproblems are few, the duplicated work is a constant factor and not worth the storage. The failure mode is specifically the exponential blow-up, where the same handful of states is visited an astronomical number of times. Finally, be precise about the vocabulary in an interview. "Overlapping subproblems" is not a synonym for "the branches read the same input": the two halves of a sorted range both read the same original data, and they still overlap in no subproblem at all. Overlap is about **identical subproblem instances**, not about shared bytes.