#39
Combination Sum
Medium Backtracking with reuse
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return all unique combinations of candidates (distinct numbers, each usable unlimited times) that sum to target.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: combinations that add to target, reusing numbers allowed.
Why this works: recurse with the same index to allow reuse; stop when a candidate is bigger than what's left.
Example: [2, 3, 6, 7], target 7
2+2+3 = 7 ✓7 = 7 ✓
✦Hints open one at a time
To allow reuse, recurse with the same index i, not i + 1.
Sort the candidates so you can stop as soon as one is bigger than what's left.
↗Approach
backtrack(start, remaining): if remaining is 0, record. Loop i from start; break if candidates[i] > remaining; otherwise add it and recurse with (i, remaining − candidates[i]).
</>Solution (Java)
import java.util.*;
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> res = new ArrayList<>();
backtrack(candidates, 0, target, new ArrayList<>(), res);
return res;
}
private void backtrack(int[] c, int start, int remaining, List<Integer> path, List<List<Integer>> res) {
if (remaining == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < c.length && c[i] <= remaining; i++) {
path.add(c[i]);
backtrack(c, i, remaining - c[i], path, res); // i, not i+1: reuse allowed
path.remove(path.size() - 1);
}
}
}!Common mistake
Recursing with start = 0 each time, which produces the same combination in different orders.
Complexity
- Time: Exponential — bounded by the number of combinations explored.
- Space: O(target / min) recursion depth.
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon