1. Target hit
A path that brings remaining to zero is a valid combination.
if (remaining === 0)Typorithm · medium
Combination Sum
▷ Interactive algorithm labcombination-sumbacktrackingunbounded-picktarget-sumchoose-explore-undo
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Combination Sum
Backtracking
Reach a target sum by choosing candidates with reuse, recursing from i so numbers can repeat.
Each candidate may be used unlimited times, so the same number can appear repeatedly in one combination.
Recursing from i instead of i + 1 is what permits reuse while still avoiding permuted duplicates.
Subtract the chosen value from remaining; hitting zero records a valid combination.
Preparing algorithm lab…
01
Recurse from i to allow reuse.
02
Base case: remaining is 0.
03
Skip candidates larger than remaining.
function combinationSum(candidates, target) {
const result = [];
function backtrack(start, path, remaining) {
if (remaining === 0) {
result.push([...path]);
return;
}
for (let i = start; i < candidates.length; i += 1) {
if (candidates[i] > remaining) continue;
path.push(candidates[i]);
backtrack(i, path, remaining - candidates[i]);
path.pop();
}
}
backtrack(0, [], target);
return result;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Prune overshoot
Skip candidates larger than what is left to reach.
if (candidates[i] > remaining) continue3. Choose
Add the candidate to the current path.
path.push(candidates[i])4. Reuse allowed
Recursing from i (not i + 1) lets the same number be reused.
backtrack(i, path, remaining - candidates[i])5. Undo
Remove the candidate to try the next one.
path.pop()A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.