Combination Sum
Combination Sum is a medium Backtracking problem from the Blind 75. The key pattern is backtracking, and a good solution runs in Exponential in target / smallest candidate time.
Problem
Return unique non-decreasing combinations of reusable positive candidates that sum to target, sorted lexicographically.
Examples
Example 1
Input
{"candidates":[2,3,5],"target":8}Output
[[2,2,2,2],[2,3,3],[3,5]]Example 2
Input
{"candidates":[3,4,7],"target":7}Output
[[3,4],[7]]Example 3
Input
{"candidates":[2],"target":1}Output
[]Approach
Sort the candidates and build combinations recursively, allowing the current candidate to be reused and never going back to smaller ones.
| Pattern | Backtracking |
|---|---|
| Time | Exponential in target / smallest candidate |
| Space | O(target / smallest candidate) |
Watch out for
Stop a branch as soon as the running sum passes the target.