Combination Sum

1. Problem & Core Objective

Given an array of distinct positive integers and a target, return all unique combinations summing to the target. The same number may be used unlimited times. Two combinations are different only if the multiset of numbers differs.

candidates = [2,3,6,7], target = 7
→ [[2,2,3], [7]]

candidates = [2,3,5], target = 8
→ [[2,2,2,2], [2,3,3], [3,5]]

Constraints: 1 <= candidates.length <= 30 · 2 <= candidates[i] <= 40 · all distinct · 1 <= target <= 40

What's actually being tested: two things that turn the generic skeleton into this specific problem — passing i instead of i + 1 to allow reuse, and pruning when the remaining target goes negative. It's the first question in the section where the search must be cut short.

2. First-Principles Thought Process

Reuse is one character

Subsets passed i + 1 to the recursive call: move past the element I just used. Here an element can be used again, so pass i: stay at this element and consider it again.

That single change is the difference between "each element at most once" and "each element unlimited times".

But why pass a start index at all?

If reuse is allowed, why not loop over every candidate at every level?

Because that generates [2,2,3], [2,3,2] and [3,2,2] — three paths to the same combination. The problem says combinations are different only if the multiset differs, so those are duplicates.

Starting the loop at i forces the chosen indices to be non-decreasing, so each multiset is reachable by exactly one path. Deduplication by construction, not by filtering.

The pruning

All candidates are positive (constraint: >= 2). So once the remaining target goes negative, adding anything makes it worse — that branch is dead.

if (remaining < 0) return;      // prune
if (remaining == 0) { record(path); return; }

Stronger still: if the candidates are sorted, then the moment candidates[i] > remaining, every later candidate is also too big, so you can break out of the loop entirely rather than continue.

The positivity constraint is what licenses both prunings. With a negative candidate present, an over-shooting sum could be brought back down and neither cut would be valid.

Why it terminates

Each level adds at least 2 to the running sum, and the target is at most 40. So the path can be at most 20 deep. Without positive values there'd be no bound at all — [0] with any target would recurse forever.

3. Solution Paths

Approach 1 — Generate all combinations, filter by sum (brute force)

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    build(candidates, 0, new ArrayList<>(), result, target);
    return result;
}

private void build(int[] c, int start, List<Integer> path,
                   List<List<Integer>> result, int target) {
    int sum = 0;
    for (int v : path) sum += v;                 // recompute every time
    if (sum == target) { result.add(new ArrayList<>(path)); return; }
    if (path.size() >= 20) return;               // arbitrary depth cap

    for (int i = start; i < c.length; i++) {
        path.add(c[i]);
        build(c, i, path, result, target);
        path.remove(path.size() - 1);
    }
}

Explore every combination and check the sum at each node.

• Time exponential, with no pruning · Space O(target / min) depth

Counter-questions on this approach

⭐ "What's missing that makes this blow up?"

The negative-target cut. This explores branches whose sum already exceeds the target, continuing to add to them until an arbitrary depth cap stops it. Every one of those branches is provably dead the moment the sum passes the target, because all candidates are positive.

With the cut, the search tree is bounded by the target; without it, only by the artificial depth limit — and if I removed that cap it would never terminate.

⭐ "It also recomputes the sum at every node. How bad is that?"

O(path.length) per node instead of O(1). The fix is to carry the remaining target down as a parameter and subtract on the way in — the running total is then free.

That's a general habit worth naming: if a recursive function recomputes something derivable from its own parameters, pass it down instead.

"Why is the depth cap needed at all?"

It isn't, once the pruning exists — positive candidates guarantee the sum strictly increases, so the search self-limits at target / min depth. The cap is a symptom of the missing cut, and it's the kind of band-aid that turns a correctness bug into a silently-incomplete answer.

Approach 2 — Backtracking with reuse and pruning (optimal)

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates);                        // enables the break
    backtrack(candidates, 0, target, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] c, int start, int remaining,
                       List<Integer> path, List<List<Integer>> result) {
    if (remaining == 0) {                           // exact hit — record
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = start; i < c.length; i++) {
        if (c[i] > remaining) break;                // sorted: everything later is bigger too

        path.add(c[i]);
        backtrack(c, i, remaining - c[i], path, result);   // i, NOT i+1 — reuse allowed
        path.remove(path.size() - 1);
    }
}

Trace — candidates = [2,3,6,7] (sorted), target = 7:

Result [[2,2,3], [7]] ✓

• Time O(n^(target/min)) worst case · Space O(target/min) depth

Counter-questions on this approach

⭐ "Why pass i rather than i + 1?"

Because reuse is allowed. i + 1 moves past the element just chosen, so it could never appear twice; i stays put and lets the loop consider it again at the next level.

That's literally the only difference from Subsets, and it's the whole "unlimited times" requirement.

⭐ "If reuse is allowed, why keep a start index at all?"

To prevent duplicate combinations. Looping over all candidates at every level would generate [2,2,3], [2,3,2] and [3,2,2] — three paths to the same multiset, which the problem counts as one.

Starting at i forces non-decreasing index order, so each multiset has exactly one representative path. It's deduplication by construction rather than by a Set at the end.

⭐ "Why break rather than continue?"

Because the array is sorted. If c[i] > remaining, then c[i+1], c[i+2] and everything after are also greater — testing them is guaranteed waste. break abandons the rest of the level in one step.

Without sorting I'd have to use continue, which still prunes but checks every remaining candidate. The sort costs O(n log n) once and saves work at every node.

⭐ "What licenses the pruning at all?"

That all candidates are positive. Once the remaining target is negative — or here, once a candidate exceeds it — no further additions can recover, because every addition makes the sum larger.

With a negative or zero candidate the cut would be invalid, and a zero would additionally make the search infinite, since [0,0,0,...] never changes the remaining target. The candidates[i] >= 2 constraint is doing real work.

"Why check remaining == 0 but not remaining < 0?"

Because the break prevents ever making it negative — a candidate larger than remaining is never added. If I used the remaining < 0 guard instead, I'd drop the sort and the break, and check after subtracting. Both are correct; the sorted version does strictly less work.

"How deep can the recursion go?"

target / min(candidates) = 40 / 2 = 20 levels. Bounded entirely by the positivity constraint. That's also the space bound.

"Could the same combination be produced twice?"

No, and it's worth being able to say why rather than testing for it: the index sequence along any path is non-decreasing, and a non-decreasing index sequence determines the multiset uniquely. So paths and multisets are in bijection.

Comparison

4. Why the Optimal Wins

The brute force explores branches whose sum has already passed the target, and without an artificial depth cap it doesn't terminate at all.

The optimal version cuts those branches at the earliest possible moment — before adding the element, not after. Two decisions do it:

1. Carry remaining down rather than recomputing the sum, so the check is O(1).
2. Sort and break, so exceeding the target abandons the whole rest of the level rather than one candidate.

And the reuse/deduplication behaviour comes entirely from the start index: i allows reuse, and starting the loop there forbids permutations of the same multiset.

The framing worth keeping:

i allows reuse, i + 1 forbids it — and either way, starting the loop at the index forces non-decreasing order, which is what makes combinations unique without a deduplication pass.

5. Java Prerequisites

Reuse vs no reuse — one character:

backtrack(c, i,     remaining - c[i], ...)   // element may be reused
backtrack(c, i + 1, remaining - c[i], ...)   // element used at most once

Carrying the remainder down

backtrack(c, i, remaining - c[i], path, result);

Cheaper and clearer than recomputing sum(path) at every node.

Sorted break vs unsorted continue

Arrays.sort(candidates);
if (c[i] > remaining) break;        // sorted: all later candidates are bigger
if (c[i] > remaining) continue;     // unsorted: must check each one

Arrays.sort on int[] is dual-pivot quicksort — in place, O(n log n), not stable (irrelevant for primitives).

6. Interview Communication Guide

Clarifying questions: Can a number be reused (yes — unlimited)? Are candidates distinct (yes; Combination Sum II is the duplicate variant)? Are they all positive (yes — this is what licenses the pruning, so confirm it)? Does order within a combination matter (no — multisets)? Can target be 0 (no, >= 1)?

The pitch

"This is the Subsets template with two changes.

First, reuse. Subsets passed i + 1 to move past the element just used; here I pass i, so the same element can be chosen again at the next level. That single character is the 'unlimited times' requirement.

But I keep the start index, because without it I'd generate [2,2,3], [2,3,2] and [3,2,2] — three paths to the same multiset, which the problem counts as one combination. Starting the loop at i forces non-decreasing index order, so each multiset has exactly one path. Deduplication by construction rather than a Set at the end.

Second, pruning. I carry the remaining target down as a parameter rather than recomputing the sum, and I sort the candidates so that when one exceeds the remaining target I can break — everything after it is larger too.

What licenses that cut is that all candidates are positive. Once the sum passes the target nothing can bring it back. With a zero candidate the search wouldn't even terminate, since [0,0,0,…] never changes the remainder — so I'd confirm the positivity constraint rather than assume it.

Depth is bounded by target / min(candidates), which is 20 here, so that's also the space.

Without the pruning this explores provably dead branches and needs an artificial depth cap to stop at all."

Edge cases to volunteer:

Name the first and last. The first checks the loop can exit with nothing recorded; the last is the deepest the recursion can go and confirms the bound is target / min.

7. Follow-Up Questions — Modified Constraints

⭐ "What if candidates could contain duplicates and each could be used only once?"

That's Combination Sum II, question 5. Two changes: pass i + 1 to forbid reuse, and skip duplicate values at the same level with if (i > start && c[i] == c[i-1]) continue;. Sorting is required for both the pruning and the skip.

⭐ "What if a candidate could be zero or negative?"

The pruning becomes invalid — an over-shooting sum could be brought back by a negative, so no branch is provably dead. And a zero makes it non-terminating, since it never reduces the remainder. You'd need an explicit depth or usage cap, and the problem becomes much closer to unbounded subset-sum.

Worth raising unprompted, because it shows the constraint was load-bearing rather than incidental.

"Count the combinations instead of listing them."

Then it's unbounded knapsack DP, not backtracking: dp[t] += dp[t - c] for each candidate, iterating targets ascending. O(n · target) — vastly faster, because counting doesn't require materialising each combination. Worth naming that enumeration and counting have genuinely different complexities here.

"Find the combination with the fewest elements."

Coin Change (LC 322) — the same DP with min instead of a sum, at O(n · target). Backtracking would work but explores exponentially many combinations to find one answer.

"What if target were 10^5?"

Depth becomes 10^5 / 2 = 50,000, so the recursion would overflow and the number of combinations explodes. Enumeration is hopeless at that scale; only the counting DP remains feasible, and even that is O(n · target).

"Return combinations in sorted order."

Sorting the candidates — which I already do for the pruning — makes each combination internally non-decreasing, and the DFS emits them in lexicographic order. So it comes free. Worth noticing that a sort added for performance also bought an ordering guarantee.