LeetCode 39 ·
Medium
Combination Sum
Find all unique combinations summing to a target, where numbers may be reused.
Try it
Step through the core mechanic. The simulator below runs the backtracking shape this problem is built on.
Interactive · Recursion call tree — Fibonacci naive recomputes; memoised short-circuits on cache hits
Mode O(2ⁿ) calls
enter fib(6)
total calls1 unique values≤ 7 modenaive
Toggle the modes.
Naive at n=6 makes 25 calls. Memoised at n=6 makes 11 calls — and the cache
hits (amber circles) are the difference. The shape of the tree changes
dramatically: naive is a fat exponential tree; memoised collapses to a
near-linear path with stub returns where the cache hits.
The approach
Backtrack with a start index so combinations are non-decreasing (avoids permutation duplicates). Recurse staying on the same index to allow reuse; prune when the remaining target goes negative.
| Aspect | Value |
|---|---|
| Pattern | Backtracking |
| Recognise it by | All combinations hitting a target, reuse allowed. |
| Time complexity | O(2^t) |
| Space complexity | O(t) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.