STEP 7 · RECURSION · SKIP EQUAL SIBLINGS · MEDIUM

Combination Sum II

WHAT IT SAYS

Given candidates that may contain duplicates, find every unique combination summing to a target, using each array element at most once.

WHAT IT'S REALLY ASKING

"Two copies of the number 1 are interchangeable — picking the first copy or the second builds the identical combination. So the duplicate is not in your array; it is in your CHOICES. When two choices at the same level are indistinguishable, which one do you keep, and what exactly does the other one add?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Recurse on i+1, then hash the answers

O(2^n * n) time, plus a set sized by the duplicates

Standard subset-style recursion: at each index either take the element or skip it, never revisit an index, and record the paths that hit the target. Then sort each answer and drop it into a set so the identical ones merge.

WHERE THE WORK IS WASTED — Each answer is discovered once for every distinct set of INDICES that spells it. Three copies of the value 1 in the array means the answer [1] surfaces three separate times, [1,1] surfaces three more, and the count of clones grows combinatorially with the multiplicity — not linearly. The set is not tidying up an edge case; it is absorbing a flood you chose to create.

KEY OBSERVATION — THE UNLOCKlink

Two identical choices at one level: the later is redundant.

Sort the array so that equal values sit next to each other. Now stand at one node of the recursion and consider picking the value v — but v appears at positions j and j' with j < j'. Both choices consume exactly one copy of v and then continue into the suffix that follows their index. Compare those two suffixes. The suffix after j strictly CONTAINS the suffix after j' — it has everything j' has, plus the elements in between. So every combination reachable by picking the copy at j' is also reachable by picking the copy at j. The later choice produces nothing new. It cannot: its entire subtree is a subtree of its sibling's. That is the proof behind the one-liner. At each level, only the FIRST occurrence of each distinct value may be chosen. In code: skip index j when j is greater than start and a[j] equals a[j-1]. And now the detail that everyone gets wrong. The guard is 'j greater than START', not 'j greater than zero'. Two equal values at the same LEVEL are redundant siblings — one of them must go. But two equal values at different DEPTHS are two different physical copies being consumed by one combination, which is exactly how [1,1] gets to exist at all. Level-wise you deduplicate; depth-wise you consume. Confuse the two and you either emit duplicates or silently lose every answer that uses a repeated value.

Sort, skip equal siblings, advance the index

O(2^n * n) worst case, but the tree now contains only distinct, living branches

Sort. Recurse with (start, remaining). Loop j from start: if j is past start and a[j] equals a[j-1], continue — that sibling's subtree is already covered. If a[j] exceeds remaining, break, since everything after it is larger. Otherwise take a[j], recurse with (j+1, remaining - a[j]) — j+1 because each element is available only once — and undo.

WHAT YOU TRADED — Sorting costs O(n log n) and buys two things at once: equal values become adjacent, so uniqueness is a neighbour check rather than a global set; and the values become monotone, so an overshoot lets you break instead of continue. The transferable one-liner: skip equal SIBLINGS, allow equal DESCENDANTS. That single sentence separates Combination Sum, Combination Sum II, Subsets II and Permutations II from one another.

WATCH THE IDEA RUN

SORTED CANDIDATES — equal neighbours are interchangeable

1dup

CALL STACK

stack empty — every branch explored

duplicate branches skipped 0

path empty

found 0

Each number may be used ONCE now — but the array contains two 1s, and they are different array slots holding the same value. Use slot 0 or slot 1 and you build the identical combination twice.

step 1 / 36

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Skip Equal Siblings

YOU'LL SEE IT AGAIN WHEN

The input contains repeats and the output must be duplicate-free — so the redundancy lives in the choice, not in the value.
Two identical choices at the same level lead to nested subtrees, which makes the later one provably redundant rather than merely suspicious.
You are tempted to serialise answers into a hash set to detect repeats — a reliable sign the recursion is over-generating on purpose.

SAME BLUEPRINT, DIFFERENT PROBLEM

Subsets IIPermutations IICombination Sum3 Sum (the same skip-the-equal-neighbour rule, on two pointers)

The bar isn't "solved it once." It's "could rebuild it from the observation."