Combination Sum
The problem
Given distinct positive integers and a nonnegative target, return all value combinations summing to the target. Each value can be reused; combinations differing only in order are the same.
Example
candidates = [2, 5, 7], target = 7 → [[2, 5], [7]]
Need a hint?
Never move backward in the candidate order while building one combination.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Sort candidates. Recurse with a start index, remaining total, and current path. Try values from start onward, stopping when a value exceeds the remainder. Recurse with the same index to allow reuse. Copy the path at remainder zero, then backtrack.
Complexity
Output-sensitive exponential time; O(target / smallest candidate) recursion depth, plus output and sorting space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.