Combination Sum

Brute Force — Why It Doesn't Scale

The naive approach would generate all possible subsets of every length, with repetition, then check which ones sum to the target. For candidates = [2, 3, 6, 7] and target = 7, we would enumerate an enormous number of combinations — most of them useless.

We need a systematic way to explore combinations without duplicates and with early termination when the running sum exceeds the target.

The Core Insight — Backtracking with Reuse

The trick is a classic backtracking pattern: at each step, we choose a candidate, add it to our current path, then recurse with a reduced target. After the recursive call returns, we undo the choice (backtrack) and try the next candidate.

Three rules govern the backtracking:

Decision Tree Walkthrough

Let's trace the backtracking for candidates = [2, 3, 6, 7], target = 7. The sorted order is already [2, 3, 6, 7]. Each node shows the current path and remaining target.

The start index parameter prevents generating duplicate combinations like [2, 3, 2] and [3, 2, 2] — once we move past candidate 2, we never go back to it. We only consider candidates at index start or later.

Edge Cases

Full Annotated Code

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);           // Sort for early termination
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int remain,
                           int start, List<Integer> path,
                           List<List<Integer>> result) {

        if (remain == 0) {               // Target reached — record solution
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++) {

            if (candidates[i] > remain)    // Prune: too large (and all after)
                break;

            path.add(candidates[i]);       // Choose

            backtrack(candidates,
                      remain - candidates[i],
                      i,                         // ← NOT i+1: allow reuse
                      path, result);

            path.remove(path.size() - 1);  // Un-choose (backtrack)
        }
    }
}

Interactive Demo

Enter candidates and a target, then step through the backtracking tree to see how combinations are built and pruned.

Complexity Analysis

Where n is the number of candidates, T is the target value, and M is the minimum candidate value. The maximum depth of the recursion tree is T/M (picking the smallest element repeatedly). At each level, we branch up to n ways.