Combination Sum

Learning goal: Recognize what must be enumerated and why repeated choices are legal.

Core idea We are not looking for one pair or one path; we must list every combination whose sum equals target. The order of values inside a combination does not matter, so [2,3,2] should not become a second answer alongside [2,2,3]. The crucial twist is that a candidate can be selected again.

Algorithm plan

• Start with an empty path and the full target as the remainder.
• Choose a candidate at or after start.
• Subtract it from the remainder and recurse.
• Record the path when the remainder is exactly zero.

Micro-example For [2,3,6,7] and target 7, choosing 2 leaves 5, and choosing 2 again leaves 3. Choosing 3 next reaches zero, producing [2,2,3].

Pitfalls

• Treating the problem like permutations creates duplicate orderings.
• Advancing past the chosen index immediately forbids reuse.
• A path with a negative remainder can never recover because all values are positive.

Recap

• Build combinations incrementally.
• Reuse is allowed.
• Use index order to avoid duplicate orderings.

Learning goal: Understand why reuse requires recursing with the same candidate index.

Core idea At a recursive call, start means "the earliest candidate that may be used next." If we choose candidates[i], we recurse with i, not i + 1, because the same value remains available. Moving to i + 1 is a separate decision: it means we stop using the current candidate and consider later values.

Algorithm plan

• At index i, branch by choosing candidates[i].
• Keep i as the next start while the candidate may be reused.
• Eventually skip to i + 1 through the loop's later iterations.
• Stop a branch once its remainder is negative.

Micro-example After choosing 2 from [2,3,6,7], the state is path = [2], remaining = 5, start = 0. Choosing index 0 again creates [2,2]; choosing index 1 instead creates [2,3].

Pitfalls

• Passing i + 1 after every pick silently changes the problem.
• Restarting from 0 allows descending orders and duplicate combinations.
• Forgetting that start controls ordering, not whether a value exists globally.

Recap

• Pick: recurse with i.
• Skip current candidate: let the loop reach i + 1.
• This separates reuse from duplicate avoidance.

Learning goal: Translate the search idea into a correct recursive procedure.

Core idea Backtracking explores one candidate choice, recursively completes that partial combination, and then removes the choice before trying the next option. Because every candidate is positive, the remainder only decreases. That gives a safe and simple pruning rule: once remaining < 0, no extension of the current path can work.

Algorithm plan

search(start, remaining, path):
    if remaining == 0:
        save a copy of path
        return
    if remaining < 0:
        return
    for i from start through the last candidate:
        path.append(candidates[i])
        search(i, remaining - candidates[i], path)
        path.pop()

The call search(i, ...) is the defining detail. It allows the selected value to be used again, while the loop's increasing indices ensure that combinations are generated in one canonical order.

Micro-example For path = [2,2] and remaining = 3, choosing index 1 adds 3, records [2,2,3], then removes 3 to restore [2,2].

Pitfalls

• Save a copy of path, not the mutable list itself.
• Backtrack after every recursive call.
• Check remaining == 0 before exploring more candidates.

Recap

• Choose, recurse, undo.
• Recurse with the chosen index.
• Prune negative remainders immediately.

Learning goal: Follow the complete search tree and see both successful and pruned branches.

Core idea The path is the current combination, while remaining is the amount still needed. At each level, the loop considers candidates from start onward. The search first explores smaller values, so it discovers [2,2,3]; later it explores the direct choice [7].

Algorithm plan

• Begin with path = [], remaining = 7, and start = 0.
• Choose 2 repeatedly by keeping start = 0.
• Add 3 when the remainder becomes 3; record the completed path.
• Backtrack, try other candidates, and prune any negative remainder.
• Eventually choose 7 from the root and record the second answer.

Micro-example The successful chain is 7 -> 5 -> 3 -> 0, corresponding to picks 2, 2, 3. Another root branch picks 7 and immediately reaches 0.

Pitfalls

• A failed branch is not an error; it is useful evidence for pruning.
• Removing the last path value must happen when returning from every branch.
• The direct [7] answer is easy to miss if the loop stops after smaller candidates.

Recap

• The same index enables [2,2,3].
• Negative remainder branches are discarded.
• The root also tries 7, yielding [7].

Learning goal: Identify the implementation mistake that most often breaks this solution.

Core idea The most dangerous bug is advancing the start index after every pick. Writing search(i + 1, ...) treats each candidate as usable at most once, which solves a different problem. Combination Sum explicitly permits repetition, so the recursive call must use i.

Data structure model

• path: the current combination under construction.
• start: the first candidate index allowed at this depth.
• remaining: target still needed.
• answers: completed path copies.

Micro-example For target 7, the valid answer [2,2,3] requires choosing index 0 twice. If the first 2 changes start to 1, the second 2 is unavailable and the answer disappears.

Pitfalls

• Forgetting to pop after recursion leaves stale values in later paths.
• Recording path by reference can make every answer change later.
• Returning only when remaining < 0 misses completed combinations at zero.
• Assuming candidates are sorted when using a sort-dependent optimization without sorting first.

Recap

• search(i, ...) means reuse is allowed.
• search(i + 1, ...) means skip the current candidate.
• Zero records; negative prunes; backtracking restores state.

Learning goal: State the cost of exhaustive combination search and remember the reusable template.

Core idea Backtracking may explore exponentially many paths because the number of valid and invalid combinations grows rapidly with the target and the candidate values. The positive-number constraint bounds the depth: a path can contain at most target / min(candidates) values. The recursion stack therefore uses space proportional to the maximum path length.

Algorithm plan

• Let m be the number of candidates.
• Explore each candidate choice from the current start index.
• Recurse with the same index to model unlimited reuse.
• Stop at zero or prune below zero.
• Include the output list in any total-space discussion because answers themselves may be large.

Micro-example With target 7 and smallest candidate 2, no path can contain more than 3 values before exceeding the target. Larger targets or smaller candidates create deeper and broader search trees.

Pitfalls

• Calling the runtime polynomial ignores the output-sensitive search tree.
• Saying space is only O(1) overlooks the recursion path.
• Forgetting that returned combinations also consume memory.

Recap

• Time is exponential in the bounded target/candidate search space.
• Auxiliary recursion space is O(target) under the usual positive-integer bound.
• The reusable template is choose, recurse with i, undo, and prune.