Combination Sum
MediumBacktracking
You get an array of different positive integers candidates and a positive target. Return every combination of candidates that adds up to target. A candidate can be used any number of times.
Two combinations are the same if they use the same numbers the same number of times, so list each one once. The combinations can come back in any order, and so can the numbers inside each.
Examples
Input: candidates = [3, 4, 5], target = 8 Output: [[3, 5], [4, 4]]
3 + 5 = 8 and 4 + 4 = 8. Using 4 twice is allowed.
Input: candidates = [5, 7], target = 3 Output: []
Every candidate is bigger than 3, so nothing adds up to it.
Constraints
1 ≤ candidates.length ≤ 302 ≤ candidates[i] ≤ 40, all different1 ≤ target ≤ 40
Stuck?
Hint 1
Build a combination one number at a time and backtrack: add a candidate, solve for the smaller target that is left, then take it back off.
Hint 2
To stop [2, 3] and [3, 2] both turning up, let each call pick only from the candidate it is on and the ones after it. Passing the same index down is what lets a number repeat.
The idea
Build each combination one number at a time, and back up once it is complete or nothing more fits. The hard part is listing each combination once. If a call may only pick the candidate it is on or later ones, every combination is built in exactly one order: the order its numbers sit in candidates.
Time O(n^(t/m)) for n candidates, target t and smallest candidate m: exponential, but small at these sizesExtra space O(t/m) for the recursion, besides the answer
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
chosen holds the combination being built. One array serves every call: a number is pushed on the way down and popped on the way back.
function combinationSum(candidates, target) { const out = []; const chosen = []; const pick = (start, left) => { if (left === 0) { out.push([...chosen]); return; } for (let i = start; i < candidates.length; i++) { if (candidates[i] > left) continue; chosen.push(candidates[i]); pick(i, left - candidates[i]); chosen.pop(); } }; pick(0, target); return out;}The trap
This version lets every call start again from the first candidate. Each combination it lists adds up to target, and none is missing, which is why it looks right. But the same numbers turn up in every order they can be picked in, so any combination that uses two different numbers is listed more than once.
function combinationSum(candidates, target) { const out = []; const chosen = []; const pick = (left) => { if (left === 0) { out.push([...chosen]); return; } for (let i = 0; i < candidates.length; i++) { // starts from 0 every time, so [2, 3] and [3, 2] both appear if (candidates[i] > left) continue; chosen.push(candidates[i]); pick(left - candidates[i]); chosen.pop(); } }; pick(target); return out;}