QuestionsDSA

Combination Sum

BacktrackingMediumDSA

Given distinct candidates and a target, return all unique combinations that sum to target. Each number may be reused unlimited times.

What it tests

Backtracking with reuse (passing `i`, not `i+1`) and pruning on remaining target.

Approach & answer

Recurse choosing candidates from `start` onward; because reuse is allowed, recurse with the same index `i`. Subtract from the remaining target and stop when it hits 0 (record) or goes negative (prune). Passing `start` prevents permuted duplicates like [2,3] and [3,2] — you only ever move forward or stay, never back. If reuse were NOT allowed you'd recurse with `i+1` instead; that single change is the difference between Combination Sum and Combination Sum II. Sorting candidates first lets you `break` early once a candidate exceeds the remainder.

Use this technique when

'All combinations summing to target', with or without reuse → backtrack; control reuse via the start index.

Complexity

Time exponential in target/min · Space O(target/min)

References

js