How do you solve Combination Sum, finding all combinations that add up to a target when numbers can be reused?
Sort the candidates and backtrack with a start index. Add a candidate, recurse with the reduced target (same start index so it can be reused), and stop a branch when the target is zero or the candidate exceeds it.
Explain it simply
You have notes of Rs 2, 3, 6 and 7 and want to pay exactly Rs 7, using any note any number of times. The order of notes does not matter, so 2+2+3 and 3+2+2 are the same payment.
To avoid repeats, only move forward through the list: once you move past a note, you never go back to it. To reuse a note, recurse with the same index. If the remaining amount hits zero, record the combination; if the next note is bigger than what is left, stop, because the list is sorted.
Example
function combinationSum(candidates, target) {
candidates.sort((a, b) => a - b);
const result = [];
const path = [];
function backtrack(start, remaining) {
if (remaining === 0) {
result.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break;
path.push(candidates[i]);
backtrack(i, remaining - candidates[i]);
path.pop();
}
}
backtrack(0, target);
return result;
}
console.log(JSON.stringify(combinationSum([2, 3, 6, 7], 7))); // Output: [[2,2,3],[7]]Complexity
Time exponential in the target divided by the smallest candidate, space O(target / smallest) for the recursion depth.
What to say in the interview
"I sort the candidates, then backtrack with a start index and a remaining target. I reuse a number by recursing with the same index, avoid permutation duplicates by never going backwards, and prune when a candidate exceeds the remainder. Time is exponential, bounded roughly by the number of valid paths."
Common mistakes
- Starting each loop from 0, which lists 2+3+2 and 2+2+3 separately.
- Not pruning, which explores branches that can never reach the target.