Combination Sum

Controlled Exploration With Reuse

Combination Sum is a structured exploration problem where you need to build valid combinations while avoiding duplicates and dead ends. Interviewers use it to test whether you can control a recursive search space with clear rules, and whether you can adapt a familiar pattern (backtracking) to handle a new wrinkle (unlimited reuse).

Problem Statement

You are given an array of distinct positive integers candidates and a target integer target.

Return all unique combinations of candidates where the chosen numbers sum to target.

You may use each number an unlimited number of times. Two combinations are considered different only if the frequency of at least one number differs.

Examples:

• 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 → []

1. Clarify Requirements Before Jumping Into Code

Before coding, restate the rules carefully.

Input: An array of distinct positive integers and a target integer.

Output: All unique combinations that sum exactly to target.

Key rules:

• Each candidate can be reused any number of times.

• [2, 2, 3] and [3, 2, 2] count as the same combination, since order inside a combination doesn't matter.

• No duplicate combinations in output.

Questions worth raising:

• Are all candidates positive? Yes - this matters because it means our sum can only grow, which enables pruning.

• Is candidates ordered? Not necessarily

• Can target be zero? Typically not in this problem, but worth confirming.

• Can the candidates array be empty? Yes. If so, return [].

2. Identify the Category of the Problem

This is a backtracking problem, the same choose → explore → unchoose pattern from Permutations and Subsets. But there are two specific twists here:

1. Reuse is allowed. Unlike Subsets, you can pick the same element multiple times.

2. There's a convergence condition. Unlike Subsets (where every state is valid), here only states where the remaining sum hits exactly zero are recorded as results.

Recognizing these two differences from problems you already know is how you adapt a familiar pattern to a new problem quickly.

3. Start With Brute Force to Build Intuition

The naive approach would be to generate every possible sequence of numbers from candidates, then filter the ones that sum to target.

The problems are immediate. Order matters in sequences, so [2, 3, 2] and [2, 2, 3] and [3, 2, 2] all get generated separately, but they're the same combination. You'd need to deduplicate afterward, which is expensive and messy.

Worse, there's no stopping condition as combinations grow: a sequence of 1s targeting 1000 is technically valid but the search space is unbounded.

While the brute-force solution is off the table, talking through these limitations points us to some ideas for controls that may need to be a part of the final solution:

• Ordering control to prevent duplicate combinations

• Pruning to stop paths that can't lead to valid combinations

4. Brainstorm More Solutions

Step 1: Learn From the Problems You've Already Solved

Think back to Subsets. The key mechanism that prevented duplicate subsets was the start index. By always moving forward in the array, we ensured we never generated [2, 3] and [3, 2] as separate results.

That same mechanism solves our ordering problem here. We can enforce the condition that combinations are always built in increasing order by ensuring we never going back to a candidate we've already passed. Then, each unique combination gets generated exactly once.

Now, how do we account for the fact that elements can be reused? In Subsets, we advanced to i + 1 after choosing element i. What needs to change?

Just one thing: when we recurse after choosing candidates[i], we pass i as the new start instead of i + 1. That means we can pick candidates[i] again on the next call, but we still can't go back to anything before it.

Step 2: Define the Recursive State

What does each recursive call need to know?

• start: The earliest index we're allowed to pick from. This enforces ordering and prevents duplicates.

• remaining: How much more we need to sum to. When this hits 0, we've found a valid combination. When it goes negative, this path is dead.

• path: The combination built so far.

At each call:

• If remaining == 0: record the current path as a valid combination.

• If remaining < 0: stop. this path overshot the target.

• Otherwise: loop from start to end of candidates, add each one, recurse with the same start index (allowing reuse), then remove it.

Step 3: Trace Through an Example

Let's trace candidates = [2, 3, 6, 7], target = 7:

backtrack(start=0, remaining=7, path=[])
  i=0: add 2 → backtrack(start=0, remaining=5, path=[2])
    i=0: add 2 → backtrack(start=0, remaining=3, path=[2,2])
      i=0: add 2 → backtrack(start=0, remaining=1, path=[2,2,2])
        i=0: add 2 → remaining=-1 → prune ✗
        i=1: add 3 → remaining=-2 → prune ✗
        i=2: add 6 → remaining=-5 → prune ✗
        i=3: add 7 → remaining=-6 → prune ✗
      remove 2
      i=1: add 3 → backtrack(start=1, remaining=0, path=[2,2,3])
        remaining==0 → record [2,2,3] ✓
      remove 3
      i=2: add 6 → remaining=-3 → prune ✗
      i=3: add 7 → remaining=-4 → prune ✗
    remove 2
    i=1: add 3 → backtrack(start=1, remaining=2, path=[2,3])
      i=1: add 3 → remaining=-1 → prune ✗
      i=2: add 6 → remaining=-4 → prune ✗
      ...all pruned
    remove 3
    ...6 and 7 also pruned (5-6<0, 5-7<0)
  remove 2
  i=1: add 3 → backtrack(start=1, remaining=4, path=[3])
    i=1: add 3 → backtrack(start=1, remaining=1, path=[3,3])
      all candidates ≥ 3, all overshoot → pruned
    remove 3
    i=2: add 6 → remaining=-2 → prune ✗
    i=3: add 7 → remaining=-3 → prune ✗
  remove 3
  i=2: add 6 → remaining=1 → all remaining candidates overshoot → pruned
  i=3: add 7 → backtrack(start=3, remaining=0, path=[7])
    remaining==0 → record [7] ✓
  remove 7

Result: [[2,2,3], [7]]. Correct.

Notice how much work the pruning eliminated. Paths that overshoot the target get cut off immediately. We never explore [2, 2, 2, 2, ...] past the point where the sum exceeds 7. This is why the "all numbers are positive" constraint matters so much: it guarantees that a sum can never recover once it overshoots, making pruning safe.

Step 4: Can We Prune Even Earlier?

Right now we prune when remaining < 0, after adding the candidate and recursing. But we could check before adding: if candidates[i] > remaining, adding it will definitely overshoot, so skip it.

If we sort candidates first, we can take this further: as soon as candidates[i] > remaining, we can break the loop entirely, because all subsequent candidates are also too large.

Arrays.sort(candidates);  // sort first

for (int i = start; i < candidates.length; i++) {
    if (candidates[i] > remaining) 
        break;  // prune early — and stop the loop
    path.add(candidates[i]);
    backtrack(candidates, i, remaining - candidates[i], path, result);
    path.remove(path.size() - 1);
}

This doesn't change worst-case complexity, but it significantly reduces the work done in practice, especially on larger inputs with many candidates.

To understand the complexity, consider what drives the recursion: the depth of any path is at most target / min(candidates). That's the longest possible combination, where you repeatedly pick the smallest candidate.

At each level of that path, you can branch to any of the k candidates (where k = candidates.length).

That gives a time complexity of roughly O(k^(target/min(candidates))) - exponential in the ratio of the target to the smallest candidate.

Space complexity is O(target / min(candidates)) for the call stack depth.

Sorting and breaking early prunes many branches in practice, but in the worst case, when the smallest candidate is 1 and the target is large, every branch gets explored and the full exponential tree is traversed.

5. Trade-Offs at a Glance

Approach	Time	Space	Notes
Brute-force sequences	Exponential	Large	Duplicate-heavy; no pruning
Backtracking	Exponential	O(target/min)	Clean, pruned, standard
Backtracking + sort + early break	Exponential	O(target/min)	Same complexity; faster in practice

The recursion depth is bounded by target / min(candidates), the longest possible valid combination. That's the space the call stack uses.

6. Pseudocode

sort candidates  (optional, but enables early break)

result = empty list

backtrack(start, remaining, path):
    if remaining == 0:
        add copy of path to result
        return

    for i from start to candidates.length - 1:
        if candidates[i] > remaining:
            break           ← safe to stop if sorted
        add candidates[i] to path
        backtrack(i, remaining - candidates[i], path)   ← i, not i+1 (allows reuse)
        remove last element from path

call backtrack(0, target, empty path)

7. Edge Cases

• No valid combination: If no subset sums to target, the result is []. The recursion simply never hits remaining == 0 on a non-negative path.

• Single candidate: candidates = [3], target = 9 → [[3, 3, 3]]. The recursion reuses the single element until the target is hit.

• Single candidate, no solution: candidates = [2], target = 3 → []. 2 overshoots with any reuse, and one copy doesn't reach 3.

• Large target with small candidates: Works correctly but may produce many results. Depth is bounded by target / min(candidates).

8. Full Solution

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

public class CombinationSum {

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

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

        if (remaining == 0) {
            // copy — don't store the reference
            result.add(new ArrayList<>(path));  
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) 
                break;  // sorted: no point continuing

            path.add(candidates[i]); // choose
            backtrack(candidates, i, remaining - candidates[i], path, result);  // explore (i, not i+1)
            path.remove(path.size() - 1); // un-choose
        }
    }
}

9. Test Your Solution

// Standard case with reuse
System.out.println(combinationSum(new int[]{2,3,6,7}, 7));
// [[2,2,3], [7]]

// Multiple valid combinations
System.out.println(combinationSum(new int[]{2,3,5}, 8));
// [[2,2,2,2], [2,3,3], [3,5]]

// No valid combination
System.out.println(combinationSum(new int[]{2}, 1));
// []

// Single candidate, exact reuse
System.out.println(combinationSum(new int[]{1}, 2));
// [[1,1]]

// Multiple paths to target
System.out.println(combinationSum(new int[]{3,4,5}, 9));
// [[3,3,3], [4,5]]

10. Key Lessons for Future Problems

• One index change separates "use once" from "reuse freely." Passing i instead of i + 1 when recursing is the entire mechanism for reuse. Understand why it works. The start index controls which candidates are available on the next call, so passing i keeps the current candidate available while still preventing you from going backward.

• The start index does double duty. It prevents duplicate combinations and controls reuse. In Subsets and Permutations, the start index just prevented duplicates. Here it also determines whether reuse is possible. Recognizing this dual role helps you reason clearly about variations.

• Positive numbers enable pruning - use it. The moment candidates[i] > remaining, you know this candidate and all larger ones are dead ends. If the array is sorted, break instead of continue. Whilt it does not affect complexity, this is the kind of optimization that distinguishes a polished solution from a merely correct one.

• Backtracking problems form a family. Permutations, Subsets, and Combination Sum all use the same skeleton. The differences are: whether you record at every level or only at leaves, whether you advance to i+1 or stay at i, and whether you have a convergence condition. Build a clear mental model of each variation and you can derive solutions to new problems rather than memorizing them.

Combination Sum teaches how to explore deeply without wandering - how to impose structure on a recursive search so that it's both complete (finds everything valid) and efficient (doesn't waste time on dead ends). That discipline shows up everywhere in technical interviews.

Good Luck and Happy Coding!