Given an array of distinct integers candidates and a target integer target, return every unique combination of candidates that sums to target.
The same candidate may be chosen an unlimited number of times. Two combinations are the same if one is a reordering of the other, so each distinct multiset of numbers must appear at most once.
You may return the combinations in any order, and the numbers within each combination in any order — any valid arrangement is accepted.
Example
2 + 2 + 3 = 7 and 7 = 7. 2 may be reused.
Constraints
- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- All elements of candidates are distinct.
- 1 <= target <= 40
Intuition
A first attempt tries every candidate at every position, with no restriction on order: at each step, add any candidate to the running path and recurse, backing off once the running sum reaches or passes the target. Whenever the sum lands exactly on the target, the path is one valid combination.
function combinationSumBruteForce(candidates, target) {
const seen = new Set(); // canonical keys of combinations already recorded, so dedup works after the fact
const result = [];
const path = []; // the combination currently being built
let sum = 0; // running total of the path
function dfs() {
if (sum === target) {
// Sort the path so any order of the same multiset maps to one canonical key.
const key = [...path].sort((a, b) => a - b).join(',');
if (!seen.has(key)) {
seen.add(key);
result.push([...path].sort((a, b) => a - b));
}
return; // stop — don't keep adding once the target is already hit
}
if (sum > target) return; // overshot; this branch can never recover
// Try every candidate at every position — no start index, so [2,3] and [3,2] both get explored.
for (let i = 0; i < candidates.length; i++) {
path.push(candidates[i]);
sum += candidates[i];
dfs();
sum -= candidates[i];
path.pop();
}
}
dfs();
return result;
}This works, but it pays twice for never restricting the order of choices. The search explores every ordering of a combination — [2, 3] and [3, 2] both get built as separate branches — which blows the branching factor up to the full candidate count at every level, not just the candidates from some point onward. Then it has to sort and dedup after the fact just to collapse those reorderings back into one answer. Can we do better?
Key observation: once reordering doesn't matter, force the search to only ever build combinations in non-decreasing order. Passing a start index forward — the earliest index the next pick may come from, instead of always scanning from 0 — means [3, 2] is never attempted as a separate branch from [2, 3]: once index 0 is behind you, start can only move further forward, never back. That's the same decision-tree recursion behind Subsets, just with a numeric budget (remaining) capping the depth instead of running out of indices — and reuse still works, because recursing with start = i (not i + 1) lets the same candidate be chosen again.
Sorting the array first buys one more win: once sorted[i] is too big for what's left, every candidate after it is too (they're sorted ascending) — so the loop can break immediately instead of checking every remaining candidate one by one.
Walking it through:
sorted: [3, 4, 5], target = 8
Start the search at start=0 with remaining=8. Reuse is allowed, so taking 3 recurses with the same start index — 3 can be chosen again next.
After picking 3 twice (path=[3,3], remaining=2), even the smallest candidate no longer fits. Because the array is sorted, everything from here on is at least as big — break instead of checking each one.
Backtracking out of the [3,3,…] and [3,4,…] dead ends, index 2 (value 5) closes the gap exactly: remaining hits 0, so [3, 5] is recorded.
Back at the root, the whole i=0 branch is exhausted. Moving to i=1 raises start to 1 — index 0's candidate (3) can never be chosen again below this point. That's exactly why [4, 3] never gets generated as a second copy of [3, 4]-style pairs: only non-decreasing picks are possible.
One level deeper, index 1 (value 4) is available again since start is still 1 — reuse in action. remaining hits 0: record [4, 4].
Finally, starting fresh from index 2 (3 and 4 are now locked out), only 5 remains: 5 > remaining(3) — break. Nothing left to try; the search ends having found exactly two combinations.
Optimization
Backtracking
Sort the candidates, then explore combinations with DFS. At each step you either take the current candidate again (allowing reuse, so you stay on the same index) or advance to the next candidate. Prune as soon as the running sum exceeds the target.
With n candidates and target T, the search tree is bounded by the number of valid combinations; worst case O(n^(T/min)) nodes, O(T/min) recursion depth.
function combinationSum(candidates, target) {
// Sort so the search can prune early: once a candidate is too big, every later one is too.
const sorted = [...candidates].sort((a, b) => a - b);
const result = [];
const path = []; // the combination currently being built
// `start` is the earliest index this call may pick from — it only ever moves forward, so
// combinations are built in non-decreasing order and reorderings (e.g. [2,3] vs [3,2]) never recur.
const dfs = (start, remaining) => {
if (remaining === 0) {
// Exact match — record a snapshot of the path.
result.push([...path]);
return;
}
for (let i = start; i < sorted.length; i++) {
// Sorted ascending, so once one candidate overshoots, all the rest do too.
if (sorted[i] > remaining) break;
path.push(sorted[i]); // choose sorted[i]
// Recurse with start = i (not i + 1) so this same candidate can be reused.
dfs(i, remaining - sorted[i]);
path.pop(); // undo the choice (backtrack) before trying the next candidate
}
};
dfs(0, target);
return result;
}Complexity analysis
Time complexity: O(n^(T/m + 1)). Here's why:
- Sorting the candidates first costs O(n log n).
- Every recursive call branches over up to
ncandidates, andremainingshrinks by at leastm(the smallest candidate) with each pick, so the recursion depth is bounded byT/m. - Compounding a branching factor of
nacross a depth ofT/mbounds the call count atO(n^(T/m)), and each call that completes a combination copies up toT/mvalues into the result.
So the overall time is bounded by O(n^(T/m + 1)) — dominated by the shape of the search tree, not the O(n log n) sort. Here n is the candidate count, T the target, and m the smallest candidate.
Space complexity: O(T/m) auxiliary. Here's why:
- The recursion stack is at most
T/mframes deep, sinceremainingdrops by at leastm— the smallest candidate — on every call. - The
patharray mirrors that same depth, holding at mostT/mchosen numbers at once. - The sorted copy of
candidatesadds another O(n).
So the extra bookkeeping is O(n + T/m). Each result.push([...path]) copies the current path into the output, so result itself can grow large (as many as O(n^(T/m)) combinations worst case) — but that's the required answer, not overhead the algorithm adds.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| candidates = [5], target = 3 | [] | Smallest no-solution case — the only candidate already exceeds the target. |
| candidates = [4], target = 12 | [[4,4,4]] | Single candidate that divides the target evenly, reused three times. |
| candidates = [6,10,20], target = 6 | [[6]] | Target equals the smallest candidate itself — the larger candidates are pruned by the sorted break before they're ever tried. |
| candidates = [3,4,6], target = 12 | [[3,3,3,3],[3,3,6],[4,4,4],[6,6]] | Several candidates reach the same target different ways, including heavy reuse of the smallest value. |
| candidates = [2,5,7], target = 14 | [[2,2,2,2,2,2,2],[2,2,5,5],[2,5,7],[7,7]] | More candidates and a larger target — combinations range from two values up to seven reused copies of the smallest. |
Try it yourself
Write your solution against the real judge before checking the reference.