Combination Sum (LC 39)

Pattern: Backtracking
Difficulty: Medium
Key Concept: Build sums with unlimited reuse of each candidate; after including candidates[i], recurse with i (not i+1) so the same value can be picked again.

Problem Statement

Given an array candidates of distinct positive integers and an integer target, return all unique combinations where the chosen numbers sum to target. The same number from candidates may be used any number of times.

Input

• candidates: int[] — distinct positive integers.
• target: positive integer.

Output

• List<List<Integer>> — each combination sums to target; no duplicate combinations (same multiset) when built in non-decreasing index order.

Example

• candidates = [2, 3, 6, 7], target = 7
• Valid: [7] and [2, 2, 3] because 2 + 2 + 3 = 7.

---

1. Algorithm & Pseudocode

Brute force

result = empty
try all sequences with repetition from candidates until sum hits or exceeds target
deduplicate combinations (expensive)

Optimal — backtracking with start index

sort candidates ascending
result = empty
path = empty

backtrack(start, remaining):
    if remaining == 0:
        result.add(copy of path)
        return
    if remaining < 0:
        return
    for i from start to len-1:
        if candidates[i] > remaining: break   // sorted positives
        path.add(candidates[i])
        backtrack(i, remaining - candidates[i])  // reuse allowed
        path.remove last

Critical detail: backtrack(i, …) keeps the same starting index so the same candidate can be chosen again. backtrack(i + 1, …) would mean “each candidate at most once” (different problem).

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Reuse — After using 2, you may use 2 again. The recursive call must not force i + 1 only; passing i allows another 2 immediately.

2. No permutation duplicates — Loop i from start onward. After you have used candidates from index start, you never append an earlier index again, so you do not get both [2,3] and [3,2] as separate answers when candidates is sorted.

3. Sort + early break — With sorted positive integers, if candidates[i] > remaining, all later values are also too large; break the loop.

4. vs. 0/1 knapsack — “Use once” would use backtrack(i + 1, remaining - c) after pick.

5. Brute force — Blind enumeration of multisets is huge; backtracking cuts when remaining < 0 or reaches 0.

---

3. The Dry Run

Sample: candidates = [2, 3, 6, 7] (sorted), target = 7.

Step	start	path	rem	Loop i (val)	Outcome
1	0	[]	7	i=0 (2)	add 2
2	0	[2]	5	i=0 (2)	add 2
3	0	[2,2]	3	i=0 (2)	add 2
4	0	[2,2,2]	1	2>1 skip; 3>1…	fail, backtrack
5	0	[2,2]	3	i=1 (3)	add 3
6	1	[2,2,3]	0	—	record [2,2,3]
7	—	unwind	—	—	other branches try more 2s/3s/6/7
8	0	[]	7	i=3 (7)	add 7
9	3	[7]	0	—	record [7]

No permutation duplicates: The for loop uses i >= start, and the recursive call passes i as the new start. So after you first pick candidates[1] = 3, every deeper choice has start >= 1 and index 0 (value 2) is never available again. That makes [3,2,2] impossible while still allowing [2,2,3] via repeated picks at index 0 before ever advancing start past 0.

---

4. Java Solution

Brute Force

Conceptually: generate combinations with repetition without structure; filter by sum. Exponential and redundant.

Time: exponential in target / min(candidate) worst case.
Space: O(depth) for path.

import java.util.*;

class SolutionBrute {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        int min = candidates[0];
        int maxLen = target / min + 2;
        dfs(0, candidates, target, new ArrayList<>(), result, 0, maxLen);
        return result;
    }

    private void dfs(int start, int[] cand, int rem, List<Integer> path,
                     List<List<Integer>> result, int depth, int maxLen) {
        if (rem == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (rem < 0 || depth > maxLen) return;
        for (int i = start; i < cand.length; i++) {
            path.add(cand[i]);
            dfs(i, cand, rem - cand[i], path, result, depth + 1, maxLen);
            path.remove(path.size() - 1);
        }
    }
}

Note: The “brute” version above is still structured DFS; a truly naive approach would lack pruning and blow up faster—interviews use LC39 optimal as the contrast.

Optimal

import java.util.*;

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

    private void backtrack(int start, int[] candidates, int rem,
                           List<Integer> path, List<List<Integer>> result) {
        if (rem == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            int c = candidates[i];
            if (c > rem) break;
            path.add(c);
            backtrack(i, candidates, rem - c, path, result);
            path.remove(path.size() - 1);
        }
    }
}

---

5. The “Java vs. Others” Edge

• backtrack(i, …) vs backtrack(i + 1, …) — The former is reuse; the latter is “use each at most once.” Easy to flip by mistake in Java or any language.
• Sort + break — Early exit when c > rem; relies on sorted array.
• Python — List slicing or list copies for answers; same backtrack structure. Java’s explicit new ArrayList<>(path) makes the copy obvious.
• Overflow — For very large target, rem stays in int on LeetCode; production code might use long for sums.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	Exponential	O(target/min) path depth	Many redundant paths without tight pruning story
Optimal	O(2^(target/min)) worst case	O(target/min) stack + output	Branching bounded by candidates; sort prunes large c

Exact bound depends on values; interview focus: reuse = same index, no duplicate combos = start index monotonic.