Combination Sum
List every unique combination of candidate numbers (each usable any number of times) that sums to a target.
Progress cannot be saved in this browser, so completed lessons will reset when you leave.
Lesson notes
Try it before you watch
Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.
Reveal the key idea
Backtrack over the candidates in order, allowing the current candidate to be chosen again, and stop a branch as soon as the running sum exceeds the target.
Pattern: Backtracking. Build a candidate one choice at a time and undo the choice when it cannot lead to a solution.
Complexity
| Measure | Bound |
|---|---|
| Time | Exponential in target / smallest candidate |
| Extra space | O(target / smallest candidate) recursion depth |
Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.