You have a set of coin denominations and an amount to make. You want every distinct way to make that amount, where each denomination can be used as many times as you like. Implement combinationsTargetSum(candidates, target) — given an array of distinct positive integers and a target sum, return all the unique combinations of candidates that add up exactly to target. Each candidate may be reused an unlimited number of times, and the same multiset of numbers must not appear twice in the output. This is the classic Combination Sum problem.
// candidates: number[] — distinct positive integers, e.g. [2, 3, 6, 7]
// target: number — a non-negative integer to sum to
// returns: number[][] — every unique combination summing to target.
// Each inner combination is sorted non-decreasing.
// The outer list is sorted (lexicographically by the numbers it contains).
function combinationsTargetSum(candidates, target): number[][];A combination is a multiset: [2, 2, 3] and [3, 2, 2] are the same combination, so only one of them appears. Order within a combination does not carry meaning — we pick the non-decreasing form as the canonical one.
combinationsTargetSum([2, 3, 6, 7], 7);
// → [[2, 2, 3], [7]]
// 2+2+3 = 7 (reusing 2 twice) and 7 alone. 6 leads nowhere: 6+anything overshoots.combinationsTargetSum([2, 3, 5], 8);
// → [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
// Three ways: four 2s; one 2 and two 3s; one 3 and one 5.combinationsTargetSum([2], 1);
// → []
// 2 already exceeds the target of 1, so there is no way to reach it.combinationsTargetSum([5], 10);
// → [[5, 5]]
// A single candidate that divides the target: use it twice.[2, 2, 2, 2] is valid from candidates = [2, ...]).[2, 2, 3] and [3, 2, 2] are the same multiset — return it once. Your output must contain no duplicate combinations.target = 0 returns [[]]. There is exactly one way to sum to zero: pick nothing. The empty combination is that one way. (target = 0 → [[]], not [].)[]. When no combination reaches a positive target, return an empty list.You'll list every distinct way to add up reusable numbers to hit a target, by walking a decision tree and backing out the moment a branch can't possibly work.
You're a cashier with an unlimited drawer of certain coins — say 2s, 3s, 6s, and 7s — and you need to make exactly 7. You don't just want to know if it's possible; you want every distinct way to do it: [2, 2, 3] and [7]. "Distinct" is the catch. [2, 2, 3] and [3, 2, 2] are the same handful of coins in a different order, so they count once. The job is to enumerate every unique multiset of candidates that sums to the target, where each candidate can be used as many times as you like.
Two forces pull against each other. You want to try every candidate at every step (unlimited reuse), but you must not count the same combination twice (no permutation duplicates). Getting both right at once is the whole problem.
Picture building a combination one number at a time. At each step you have a remaining amount still to make, and you pick a candidate to subtract from it. Pick 2 from a remaining of 5, and you recurse with remaining 3. Keep going until remaining hits exactly 0 (a hit — record the path) or drops below 0 (an overshoot — abandon this branch). Every root-to-leaf path through this tree is one attempt at a combination.
This shape — try a choice, recurse, then undo the choice and try the next — is backtracking. The undo step (removing the number you just added before trying the next candidate) is what lets one array, path, be reused for every branch instead of allocating a fresh array per node.
The obvious version: recurse over every position, trying every candidate each time, collect everything that sums to the target, then throw away duplicates with a Set.
function combinationsTargetSumNaive(candidates, target) {
const hits = [];
function explore(remaining, path) {
if (remaining === 0) {
hits.push([...path]);
return;
}
if (remaining < 0) return;
for (const c of candidates) { // every candidate, every time
explore(remaining - c, [...path, c]);
}
}
explore(target, []);
// Deduplicate: sort each hit, join to a string key, keep first seen.
const seen = new Set();
const result = [];
for (const hit of hits) {
const key = [...hit].sort((a, b) => a - b).join(',');
if (!seen.has(key)) {
seen.add(key);
result.push([...hit].sort((a, b) => a - b));
}
}
return result;
}This returns the right combinations, but it works far too hard. Because the loop tries every candidate at every position, it generates [2, 3] and [3, 2] and [2, 2, 3] and [3, 2, 2] and [2, 3, 2] — every ordering of every winning multiset. For a target like 32 with small candidates, that's an explosion of permutations, almost all of which collapse to the same handful of combinations once you dedup. You're paying to generate thousands of paths, then paying again to sort-and-key each one, then throwing most away. And the dedup is fiddly: forget to sort before keying and [2, 3] and [3, 2] produce different keys, so duplicates leak through.
The waste and the bug both come from the same root: the loop is allowed to go backwards to an earlier candidate. If we forbid that, both problems vanish.
The fix is a start index. Each recursive call is told the earliest candidate index it's allowed to pick. By only ever picking candidates at or after start, every combination is built in non-decreasing order — so [3, 2] can never be born, and the Set disappears entirely.
function combinationsTargetSum(candidates, target) {
// Sort so the prune below is valid and output comes out in canonical order.
const sorted = [...candidates].sort((a, b) => a - b);
const result = [];
const path = []; // the combination we're currently building
function backtrack(start, remaining) {
if (remaining === 0) {
result.push([...path]); // copy: path keeps mutating after this
return;
}
for (let i = start; i < sorted.length; i++) {
const candidate = sorted[i];
// Sorted, so if this one overshoots, every later one does too.
if (candidate > remaining) break;
path.push(candidate);
// Recurse with i (NOT i + 1): the same candidate may be reused.
backtrack(i, remaining - candidate);
path.pop(); // undo before trying the next candidate
}
}
backtrack(0, target);
return result;
}
module.exports = { combinationsTargetSum };Three lines carry the whole idea. The start parameter is the no-going-back rule: the loop begins at i = start, never earlier, so combinations only ever grow in non-decreasing order — duplicates are impossible by construction. backtrack(i, ...), not backtrack(i + 1, ...) is what allows unlimited reuse: passing i lets the next level pick the same candidate again (that's how [2, 2, 2, 2] happens), while passing i + 1 would forbid reuse (that's the variant in Going further). if (candidate > remaining) break is the prune: because sorted is ascending, the first candidate that overshoots guarantees every later candidate overshoots too, so one break discards the entire tail of the loop.
Sorting up front buys two things at once. It makes the break prune valid (you can only break on the first overshoot if the rest are larger), and it makes the output come out already in canonical order — each combination is non-decreasing because we pick ascending, and the outer list is sorted because the loop tries smaller candidates before larger ones. No post-processing sort needed.
The prune deserves its own picture, because it's the difference between a tight tree and a sprawling one.
Trace combinationsTargetSum([2, 3, 6, 7], 7). After sorting, sorted = [2, 3, 6, 7]. We call backtrack(0, 7) with an empty path.
backtrack(start=0, rem=7) path=[]
i=0 candidate=2 (2 <= 7) push 2 -> path=[2]
backtrack(start=0, rem=5) path=[2]
i=0 candidate=2 push 2 -> path=[2,2]
backtrack(start=0, rem=3) path=[2,2]
i=0 candidate=2 push 2 -> path=[2,2,2]
backtrack(start=0, rem=1) path=[2,2,2]
i=0 candidate=2 (2 > 1) -> BREAK (prune: nothing fits)
pop -> path=[2,2]
i=1 candidate=3 push 3 -> path=[2,2,3]
backtrack(start=1, rem=0) -> HIT, record [2,2,3]
pop -> path=[2,2]
i=2 candidate=6 (6 > 3) -> BREAK
pop -> path=[2]
i=1 candidate=3 push 3 -> path=[2,3]
backtrack(start=1, rem=2) path=[2,3]
i=1 candidate=3 (3 > 2) -> BREAK
pop -> path=[2]
i=2 candidate=6 (6 > 5) -> BREAK
pop -> path=[]
i=1 candidate=3 push 3 -> path=[3]
backtrack(start=1, rem=4) path=[3]
i=1 candidate=3 push 3 -> path=[3,3]
backtrack(start=1, rem=1)
i=1 candidate=3 (3 > 1) -> BREAK
pop -> path=[3]
i=2 candidate=6 (6 > 4) -> BREAK
pop -> path=[]
i=2 candidate=6 push 6 -> path=[6]
backtrack(start=2, rem=1)
i=2 candidate=6 (6 > 1) -> BREAK
pop -> path=[]
i=3 candidate=7 push 7 -> path=[7]
backtrack(start=3, rem=0) -> HIT, record [7]
pop -> path=[]
return [[2,2,3], [7]]
Two things to watch. First, the prune firing on rem=1: candidate 2 already exceeds 1, so break skips 3, 6, and 7 in one step — no wasted recursion. Second, when we took the i=1 branch (push 3), the recursive call got start=1, so it could no longer reach back to candidate 2. That's exactly why [3, 2, 2] never appears: once you've moved past 2, you can't return to it. The result comes out as [[2, 2, 3], [7]] — already in canonical order, no dedup pass required.
0 (or for (const c of candidates)) on every recursive call, you generate [2, 3] and [3, 2] as separate paths. They're the same combination. The fix is the start parameter: each call may only pick candidates at index >= start, forcing every combination into non-decreasing order so duplicates can't form. Don't "fix" this by deduping with a Set afterward — that's the slow first attempt.i, not i + 1. This is the single easiest line to get wrong. backtrack(i, ...) lets the next level pick the same candidate again, which is how you get [2, 2, 2, 2]. If you write backtrack(i + 1, ...), you forbid reuse — you've silently solved a different problem (each candidate used at most once; see Going further). The tests with repeated values like [2, 2, 2, 2] catch this immediately.if (candidate > remaining) break line is only correct if every candidate after i is >= candidates[i]. On an unsorted array like [7, 2, 3], hitting 7 first would break and you'd never try 2 or 3 — wrong answers. Sort first, then break is safe. (If you'd rather not sort, replace break with continue — correct but slower, since it tests every candidate instead of stopping at the first overshoot.)result.push(path) pushes a reference to the array you keep mutating — every entry ends up pointing at the same (eventually empty) array. You must push a copy: result.push([...path]). Forget the spread and your result is full of identical garbage.target = 0 base case. When remaining reaches 0, you record the current path and return. Called with target = 0 directly, the very first backtrack(0, 0) records the empty path and returns [[]] — one way to sum to zero: pick nothing. That's why the contract is [[]], not []. Make sure the remaining === 0 check comes before the loop so the empty combination is recorded.remaining < 0 at the top of backtrack and never prune. But without the prune (or without sorting), deep targets with small candidates explore far more dead-end branches before bottoming out. Sort plus break keeps the tree tight.i + 1 instead of i, and add a sibling-skip: if (i > start && sorted[i] === sorted[i - 1]) continue; so two equal candidates at the same tree level don't produce duplicate combinations. The skip is the new subtlety — equal values used at different depths are fine, but two of them as the first pick of the same call would repeat a combination.ways[amount] filled with for (const c of candidates) for (let a = c; a <= target; a++) ways[a] += ways[a - c] runs in O(target × candidates.length) and sidesteps the exponential blow-up of enumerating every combination. This is the classic coin-change-count problem.k numbers (Combination Sum III is "k numbers from 1–9 summing to n"). Add a path.length check: only record a hit when remaining === 0 && path.length === k, and prune branches where path.length > k. The start-index skeleton is identical; only the base case and one prune change.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
You have a set of coin denominations and an amount to make. You want every distinct way to make that amount, where each denomination can be used as many times as you like. Implement combinationsTargetSum(candidates, target) — given an array of distinct positive integers and a target sum, return all the unique combinations of candidates that add up exactly to target. Each candidate may be reused an unlimited number of times, and the same multiset of numbers must not appear twice in the output. This is the classic Combination Sum problem.
// candidates: number[] — distinct positive integers, e.g. [2, 3, 6, 7]
// target: number — a non-negative integer to sum to
// returns: number[][] — every unique combination summing to target.
// Each inner combination is sorted non-decreasing.
// The outer list is sorted (lexicographically by the numbers it contains).
function combinationsTargetSum(candidates, target): number[][];A combination is a multiset: [2, 2, 3] and [3, 2, 2] are the same combination, so only one of them appears. Order within a combination does not carry meaning — we pick the non-decreasing form as the canonical one.
combinationsTargetSum([2, 3, 6, 7], 7);
// → [[2, 2, 3], [7]]
// 2+2+3 = 7 (reusing 2 twice) and 7 alone. 6 leads nowhere: 6+anything overshoots.combinationsTargetSum([2, 3, 5], 8);
// → [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
// Three ways: four 2s; one 2 and two 3s; one 3 and one 5.combinationsTargetSum([2], 1);
// → []
// 2 already exceeds the target of 1, so there is no way to reach it.combinationsTargetSum([5], 10);
// → [[5, 5]]
// A single candidate that divides the target: use it twice.[2, 2, 2, 2] is valid from candidates = [2, ...]).[2, 2, 3] and [3, 2, 2] are the same multiset — return it once. Your output must contain no duplicate combinations.target = 0 returns [[]]. There is exactly one way to sum to zero: pick nothing. The empty combination is that one way. (target = 0 → [[]], not [].)[]. When no combination reaches a positive target, return an empty list.You'll list every distinct way to add up reusable numbers to hit a target, by walking a decision tree and backing out the moment a branch can't possibly work.
You're a cashier with an unlimited drawer of certain coins — say 2s, 3s, 6s, and 7s — and you need to make exactly 7. You don't just want to know if it's possible; you want every distinct way to do it: [2, 2, 3] and [7]. "Distinct" is the catch. [2, 2, 3] and [3, 2, 2] are the same handful of coins in a different order, so they count once. The job is to enumerate every unique multiset of candidates that sums to the target, where each candidate can be used as many times as you like.
Two forces pull against each other. You want to try every candidate at every step (unlimited reuse), but you must not count the same combination twice (no permutation duplicates). Getting both right at once is the whole problem.
Picture building a combination one number at a time. At each step you have a remaining amount still to make, and you pick a candidate to subtract from it. Pick 2 from a remaining of 5, and you recurse with remaining 3. Keep going until remaining hits exactly 0 (a hit — record the path) or drops below 0 (an overshoot — abandon this branch). Every root-to-leaf path through this tree is one attempt at a combination.
This shape — try a choice, recurse, then undo the choice and try the next — is backtracking. The undo step (removing the number you just added before trying the next candidate) is what lets one array, path, be reused for every branch instead of allocating a fresh array per node.
The obvious version: recurse over every position, trying every candidate each time, collect everything that sums to the target, then throw away duplicates with a Set.
function combinationsTargetSumNaive(candidates, target) {
const hits = [];
function explore(remaining, path) {
if (remaining === 0) {
hits.push([...path]);
return;
}
if (remaining < 0) return;
for (const c of candidates) { // every candidate, every time
explore(remaining - c, [...path, c]);
}
}
explore(target, []);
// Deduplicate: sort each hit, join to a string key, keep first seen.
const seen = new Set();
const result = [];
for (const hit of hits) {
const key = [...hit].sort((a, b) => a - b).join(',');
if (!seen.has(key)) {
seen.add(key);
result.push([...hit].sort((a, b) => a - b));
}
}
return result;
}This returns the right combinations, but it works far too hard. Because the loop tries every candidate at every position, it generates [2, 3] and [3, 2] and [2, 2, 3] and [3, 2, 2] and [2, 3, 2] — every ordering of every winning multiset. For a target like 32 with small candidates, that's an explosion of permutations, almost all of which collapse to the same handful of combinations once you dedup. You're paying to generate thousands of paths, then paying again to sort-and-key each one, then throwing most away. And the dedup is fiddly: forget to sort before keying and [2, 3] and [3, 2] produce different keys, so duplicates leak through.
The waste and the bug both come from the same root: the loop is allowed to go backwards to an earlier candidate. If we forbid that, both problems vanish.
The fix is a start index. Each recursive call is told the earliest candidate index it's allowed to pick. By only ever picking candidates at or after start, every combination is built in non-decreasing order — so [3, 2] can never be born, and the Set disappears entirely.
function combinationsTargetSum(candidates, target) {
// Sort so the prune below is valid and output comes out in canonical order.
const sorted = [...candidates].sort((a, b) => a - b);
const result = [];
const path = []; // the combination we're currently building
function backtrack(start, remaining) {
if (remaining === 0) {
result.push([...path]); // copy: path keeps mutating after this
return;
}
for (let i = start; i < sorted.length; i++) {
const candidate = sorted[i];
// Sorted, so if this one overshoots, every later one does too.
if (candidate > remaining) break;
path.push(candidate);
// Recurse with i (NOT i + 1): the same candidate may be reused.
backtrack(i, remaining - candidate);
path.pop(); // undo before trying the next candidate
}
}
backtrack(0, target);
return result;
}
module.exports = { combinationsTargetSum };Three lines carry the whole idea. The start parameter is the no-going-back rule: the loop begins at i = start, never earlier, so combinations only ever grow in non-decreasing order — duplicates are impossible by construction. backtrack(i, ...), not backtrack(i + 1, ...) is what allows unlimited reuse: passing i lets the next level pick the same candidate again (that's how [2, 2, 2, 2] happens), while passing i + 1 would forbid reuse (that's the variant in Going further). if (candidate > remaining) break is the prune: because sorted is ascending, the first candidate that overshoots guarantees every later candidate overshoots too, so one break discards the entire tail of the loop.
Sorting up front buys two things at once. It makes the break prune valid (you can only break on the first overshoot if the rest are larger), and it makes the output come out already in canonical order — each combination is non-decreasing because we pick ascending, and the outer list is sorted because the loop tries smaller candidates before larger ones. No post-processing sort needed.
The prune deserves its own picture, because it's the difference between a tight tree and a sprawling one.
Trace combinationsTargetSum([2, 3, 6, 7], 7). After sorting, sorted = [2, 3, 6, 7]. We call backtrack(0, 7) with an empty path.
backtrack(start=0, rem=7) path=[]
i=0 candidate=2 (2 <= 7) push 2 -> path=[2]
backtrack(start=0, rem=5) path=[2]
i=0 candidate=2 push 2 -> path=[2,2]
backtrack(start=0, rem=3) path=[2,2]
i=0 candidate=2 push 2 -> path=[2,2,2]
backtrack(start=0, rem=1) path=[2,2,2]
i=0 candidate=2 (2 > 1) -> BREAK (prune: nothing fits)
pop -> path=[2,2]
i=1 candidate=3 push 3 -> path=[2,2,3]
backtrack(start=1, rem=0) -> HIT, record [2,2,3]
pop -> path=[2,2]
i=2 candidate=6 (6 > 3) -> BREAK
pop -> path=[2]
i=1 candidate=3 push 3 -> path=[2,3]
backtrack(start=1, rem=2) path=[2,3]
i=1 candidate=3 (3 > 2) -> BREAK
pop -> path=[2]
i=2 candidate=6 (6 > 5) -> BREAK
pop -> path=[]
i=1 candidate=3 push 3 -> path=[3]
backtrack(start=1, rem=4) path=[3]
i=1 candidate=3 push 3 -> path=[3,3]
backtrack(start=1, rem=1)
i=1 candidate=3 (3 > 1) -> BREAK
pop -> path=[3]
i=2 candidate=6 (6 > 4) -> BREAK
pop -> path=[]
i=2 candidate=6 push 6 -> path=[6]
backtrack(start=2, rem=1)
i=2 candidate=6 (6 > 1) -> BREAK
pop -> path=[]
i=3 candidate=7 push 7 -> path=[7]
backtrack(start=3, rem=0) -> HIT, record [7]
pop -> path=[]
return [[2,2,3], [7]]
Two things to watch. First, the prune firing on rem=1: candidate 2 already exceeds 1, so break skips 3, 6, and 7 in one step — no wasted recursion. Second, when we took the i=1 branch (push 3), the recursive call got start=1, so it could no longer reach back to candidate 2. That's exactly why [3, 2, 2] never appears: once you've moved past 2, you can't return to it. The result comes out as [[2, 2, 3], [7]] — already in canonical order, no dedup pass required.
0 (or for (const c of candidates)) on every recursive call, you generate [2, 3] and [3, 2] as separate paths. They're the same combination. The fix is the start parameter: each call may only pick candidates at index >= start, forcing every combination into non-decreasing order so duplicates can't form. Don't "fix" this by deduping with a Set afterward — that's the slow first attempt.i, not i + 1. This is the single easiest line to get wrong. backtrack(i, ...) lets the next level pick the same candidate again, which is how you get [2, 2, 2, 2]. If you write backtrack(i + 1, ...), you forbid reuse — you've silently solved a different problem (each candidate used at most once; see Going further). The tests with repeated values like [2, 2, 2, 2] catch this immediately.if (candidate > remaining) break line is only correct if every candidate after i is >= candidates[i]. On an unsorted array like [7, 2, 3], hitting 7 first would break and you'd never try 2 or 3 — wrong answers. Sort first, then break is safe. (If you'd rather not sort, replace break with continue — correct but slower, since it tests every candidate instead of stopping at the first overshoot.)result.push(path) pushes a reference to the array you keep mutating — every entry ends up pointing at the same (eventually empty) array. You must push a copy: result.push([...path]). Forget the spread and your result is full of identical garbage.target = 0 base case. When remaining reaches 0, you record the current path and return. Called with target = 0 directly, the very first backtrack(0, 0) records the empty path and returns [[]] — one way to sum to zero: pick nothing. That's why the contract is [[]], not []. Make sure the remaining === 0 check comes before the loop so the empty combination is recorded.remaining < 0 at the top of backtrack and never prune. But without the prune (or without sorting), deep targets with small candidates explore far more dead-end branches before bottoming out. Sort plus break keeps the tree tight.i + 1 instead of i, and add a sibling-skip: if (i > start && sorted[i] === sorted[i - 1]) continue; so two equal candidates at the same tree level don't produce duplicate combinations. The skip is the new subtlety — equal values used at different depths are fine, but two of them as the first pick of the same call would repeat a combination.ways[amount] filled with for (const c of candidates) for (let a = c; a <= target; a++) ways[a] += ways[a - c] runs in O(target × candidates.length) and sidesteps the exponential blow-up of enumerating every combination. This is the classic coin-change-count problem.k numbers (Combination Sum III is "k numbers from 1–9 summing to n"). Add a path.length check: only record a hit when remaining === 0 && path.length === k, and prune branches where path.length > k. The start-index skeleton is identical; only the base case and one prune change.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.