39. Combination Sum

Combination Sum is the problem that makes the reuse a number branch of backtracking click. The whole solution turns on one index you pass to the recursive call, and getting that index right is the difference between “each number once” and “each number as many times as you like.” It sits in the backtracking pattern, where the shape — choose, recurse, undo — repeats across a dozen problems.

The problem

You’re given a list of distinct positive integers and a target. Return every unique combination that sums to the target, where a number may be picked as many times as you want. Order inside a combination doesn’t matter, so [2,2,3] and [3,2,2] count as the same answer. (Full statement on LeetCode.)

For candidates = [2, 4] and target = 6, the answers are [2, 2, 2] and [2, 4] — 4 + 2 is not a third answer, it’s just [2, 4] written backward.

Intuition: a start index that never moves backward

The trap here is duplicate combinations. If at every step you were free to pick any candidate, you’d generate [2,4] and [4,2] and then have to dedupe them. The fix is to enforce an order on how you build a combination: once you’ve moved past a candidate, you never reach back for it again.

That’s what a start index buys you. Each recursive call may only use candidates from start onward. So a combination is always built in non-decreasing index order, and [4,2] simply can never be produced.

Now the reuse rule. Because you can pick the same number again, the recursive call passes i — the current index — not i + 1:

$\text{recurse}(\text{start} = i) \;\text{reuses candidate } i, \qquad \text{recurse}(\text{start} = i+1) \;\text{moves on.}$

That single choice is the entire difference between this problem and Combination Sum II. Pass i, and [2,2,2] is reachable. Pass i + 1, and each candidate is used at most once.

Sorting the candidates first adds a clean prune. Once candidates[i] alone exceeds what’s left of the target, every later candidate is even bigger, so you can stop the loop instead of testing each one.

Solution

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);        // lets us break early once a candidate overshoots
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int remaining, int start,
                           List<Integer> current, List<List<Integer>> result) {
        if (remaining == 0) {           // current sums exactly to target — record a copy
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break;   // sorted, so nothing after fits either
            current.add(candidates[i]);
            // pass i (not i + 1) so candidates[i] can be reused in the next call
            backtrack(candidates, remaining - candidates[i], i, current, result);
            current.remove(current.size() - 1);     // undo before trying the next candidate
        }
    }
}

The three lines inside the loop are the backtracking heartbeat: add a choice, recurse on the smaller problem, remove the choice. Copying current into a fresh ArrayList on success matters — current is mutated in place all the way down, so storing it directly would leave you with a list of references to the same emptied object.

Complexity

Let $t$ be the target, $m$ the smallest candidate, and $d = \lfloor t/m \rfloor$ the deepest the recursion can go. Let $R$ be the number of combinations found.

	Cost
Time	$O(n \log n) + O(\text{nodes in the search tree}) + O(R \cdot d)$
Auxiliary space	$O(d + \log n)$ (recursion depth + current, plus the sort’s stack)
Output space	$O(R \cdot d)$

The $n \log n$ is the initial sort; the search-tree term dominates and is exponential in the worst case (roughly $O(n^{\,d})$), though the target cap and the sorted prune keep real inputs far below it — which is why LeetCode can guarantee the answer count stays small. The $R \cdot d$ shows up twice: once to copy each finished combination and once to hold the output. Counting only auxiliary space, it’s $O(d)$ for the backtracking plus the $O(\log n)$ stack that Arrays.sort on a primitive array uses.

In an interview

Say the ordering insight out loud before writing anything: “I’ll use a start index so combinations are built in non-decreasing order — that’s what stops me from generating [2,4] and [4,2] as separate answers.” Then, when you write the recursive call, narrate why it’s i and not i + 1. That one line is the thing interviewers are actually probing, and reaching for i + 1 out of habit is the single most common way this solution silently becomes Combination Sum II.

The other detail worth flagging is the copy on the base case — plenty of people store current directly and get a result full of empty lists, which is a miserable bug to find under pressure.

For more on the choose-recurse-undo skeleton and where the reuse-vs-move-on decision recurs, see the backtracking pattern hub. Word Search is a good next rep: same backtracking spine, but the “undo” step is unmarking a grid cell instead of popping a number.

References

• LeetCode 39 — Combination Sum