LeetCode 39 – Combination Sum | Love Me Some Coding

Combination Sum is the backtracking template with one twist: candidates may be reused without limit. That single requirement changes exactly one character in the recursive call, and getting it right — along with the start index that stops permutations of the same combination — is the whole problem.

The problem

Given distinct positive candidates and a target, find every unique combination summing to the target. The same candidate may be used any number of times. Two combinations are different only if the multiset of numbers differs — order does not matter.

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]]
candidates = [2],       target = 1  -> []

[2,2,3] and [2,3,2] are the SAME combination. Only one may appear.

Two index rules, two different jobs

Backtracking here means: pick a candidate, subtract it from the remaining target, recurse, then undo the pick. The two decisions that shape the output are both about which index the recursion is allowed to start from.

Recurse from i, not i + 1. That is what allows reuse — the same candidate is still available at the next level down. i + 1 would solve Combination Sum II instead, where each candidate may be used once.

Never recurse from before start. This is what prevents duplicates, and it deserves more than a shrug. Without it, the search would find [2,2,3] and [2,3,2] and [3,2,2] — the same combination three times. Forbidding a smaller index than the one you arrived at forces every combination to be generated in non-decreasing order, and each multiset has exactly one non-decreasing arrangement. The uniqueness is structural; there is nothing to de-duplicate afterwards.

Note what makes this safe: all candidates are positive. The remaining target strictly decreases at every step, so the recursion has to terminate. With a zero or a negative in the input, unlimited reuse means infinite recursion, and it is worth asking about if the constraint is not stated.

Sorting is optional, and worth it

The problem does not require sorted input, and the algorithm is correct without it. Sorting buys one line: once candidates[i] exceeds what remains, every later candidate does too, so the loop can break instead of continue. On a wide candidate list that prunes a lot of dead branches for O(n log n) paid once.

Java

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);      // only so the loop below can break early
        backtrack(result, new ArrayList<>(), candidates, 0, target);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> path,
                           int[] candidates, int start, int remaining) {
        if (remaining == 0) {
            result.add(new ArrayList<>(path));   // copy: path keeps mutating
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break;   // sorted, so the rest are bigger too

            path.add(candidates[i]);
            // i, not i + 1: the same candidate stays available.
            backtrack(result, path, candidates, i, remaining - candidates[i]);
            path.remove(path.size() - 1);           // undo
        }
    }
}

new ArrayList<>(path) at the base case is not optional. path is one shared, constantly-mutating list; adding it directly would leave every entry in the result pointing at the same object, which ends up empty. The same trap appears in Generate Parentheses.

Because the loop breaks on candidates[i] > remaining, no branch is ever explored that would overshoot, and the only base case needed is remaining == 0 — there is no remaining < 0 to catch.

Python

class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        result = []
        path = []

        def backtrack(start: int, remaining: int) -> None:
            if remaining == 0:
                result.append(path[:])          # copy: path keeps mutating
                return

            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break                        # sorted: everything after is bigger

                path.append(candidates[i])
                backtrack(i, remaining - candidates[i])   # i, not i + 1
                path.pop()                                # undo

        backtrack(0, target)
        return result

path[:] is the Python copy idiom; result.append(path) stores a reference and produces a list of empty lists.

Complexity

Hard to state tightly, and interviewers know it. The bound usually quoted is O(n^{T/m + 1}) where T is the target and m the smallest candidate — the recursion tree has branching factor n and depth at most T/m, because each step subtracts at least m. Space is O(T/m) for the recursion stack and the path, not counting the output.

What actually matters in the room is the reasoning, not the formula: "the depth is bounded by target over the smallest candidate, because every pick subtracts at least that much; the branching is the number of candidates; and copying each result costs its length."

The family

Combination Sum II (40) — each candidate used once, input may contain duplicates. i + 1 instead of i, plus a same-depth skip.
Combination Sum III (216) — digits 1–9, each once, and exactly k of them. Adds a second base-case condition on the path length.
Combination Sum IV (377) — a misnomer: order does matter, so it counts permutations. That makes it a plain DP, not backtracking, and enumerating would be far too slow.

What the interviewer is checking

That the recursive call passes i, and that you can say why i + 1 would be a different problem.
That you can explain how start makes the results unique, rather than filtering duplicates out at the end.
That you copy the path into the result.
That you undo the pick after recursing.
That you notice all-positive candidates are what guarantee termination.
An unreachable target returning an empty list, not null.