Combination Sum: backtracking with unlimited reuse

The previous problem in this series, Subsets, made a binary decision at each element: include or skip. Clean and unconditional. Combination Sum introduces two complications at once — a sum constraint, and the ability to reuse any element as many times as you want. That second rule is the one that trips people up. It sounds like it should make the problem harder, but if you handle it correctly it actually simplifies the duplicate-avoidance logic.

LeetCode 39: given an array of distinct integers and a target, find all unique combinations that sum to the target. You can use any element any number of times. The problem guarantees at most 150 valid combinations for the given test cases.

What the constraints force

1 <= candidates.length <= 30. Thirty elements. Combined with 1 <= target <= 40 and 2 <= candidates[i] <= 40, the search space is heavily bounded. The minimum value is 2, which means the deepest any combination can go is target / 2 = 20 levels deep (if you're repeatedly picking 2 to reach 40). The branching factor is at most 30, but pruning cuts it dramatically in practice. This is the regime where backtracking is the natural fit — not DP, not BFS, backtracking.

2 <= candidates[i] <= 40. No zeros, no negatives. This is load-bearing. If candidates could contain 1, a combination targeting 40 could be 40 ones deep — the recursion tree explodes. The constraint candidates[i] >= 2 bounds the depth at target / min(candidates). At worst that's 40 / 2 = 20, which is fine.

All elements are distinct. This means the only source of duplicate combinations is the search order, not the input. You don't need to deduplicate on the way out. You just need to make sure the search itself doesn't generate [2, 3] and [3, 2] as separate answers.

Brute force: what happens without index control

The naive approach: at each recursive call, try every element in candidates from the beginning. Keep a running sum; when it hits target, record a copy. When it exceeds target, stop.

class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        result = []
 
        def backtrack(current: list[int], remaining: int) -> None:
            if remaining == 0:
                result.append(current[:])
                return
            if remaining < 0:
                return
            for num in candidates:
                current.append(num)
                backtrack(current, remaining - num)
                current.pop()
 
        backtrack([], target)
        return result

public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        var result = new List<IList<int>>();
 
        void Backtrack(List<int> current, int remaining) {
            if (remaining == 0) {
                result.Add(new List<int>(current));
                return;
            }
            if (remaining < 0) return;
            foreach (int num in candidates) {
                current.Add(num);
                Backtrack(current, remaining - num);
                current.RemoveAt(current.Count - 1);
            }
        }
 
        Backtrack(new List<int>(), target);
        return result;
    }
}

This is correct in the sense that it finds valid combinations. It is not correct in the sense that it produces unique combinations. For candidates = [2, 3], target = 5, it generates both [2, 3] and [3, 2]. The problem says these are the same combination because they contain the same multiset of elements — only the frequency matters, not the order.

So the brute force approach generates duplicate answers. You could deduplicate the result by sorting each combination and putting them in a set, but that's extra work on top of an already over-explored search space. The real fix is to control which elements the recursive call is allowed to consider.

Time: O(N^(T/M)) where N is the number of candidates, T is target, M is the minimum candidate value. Space: O(T/M) for the recursion stack. The call depth is bounded by how many times you can subtract the minimum value from target before going negative.

I wouldn't ship this. The duplicate problem alone disqualifies it. I include it because it's the natural first attempt and understanding why it fails makes the fix obvious.

Optimized backtracking: sort and prune

The key insight is simple. If you process candidates in order and each recursive call only considers elements at or after the current position, you can never generate [3, 2] after [2, 3]. The index acts as a one-way door: you move forward, never backward.

Sorting the array first enables a second improvement: early termination. If candidates[i] > remaining, then candidates[i+1], candidates[i+2], and everything after are also greater (array is sorted). You can break the loop instead of continuing to recurse into guaranteed failures.

class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        result = []
 
        def backtrack(start: int, current: list[int], remaining: int) -> None:
            if remaining == 0:
                result.append(current[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break  # sorted — everything after is also too large
                current.append(candidates[i])
                backtrack(i, current, remaining - candidates[i])  # i, not i+1 — reuse allowed
                current.pop()
 
        backtrack(0, [], target)
        return result

public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        Array.Sort(candidates);
        var result = new List<IList<int>>();
 
        void Backtrack(int start, List<int> current, int remaining) {
            if (remaining == 0) {
                result.Add(new List<int>(current));
                return;
            }
            for (int i = start; i < candidates.Length; i++) {
                if (candidates[i] > remaining) break;
                current.Add(candidates[i]);
                Backtrack(i, current, remaining - candidates[i]);  // i, not i+1
                current.RemoveAt(current.Count - 1);
            }
        }
 
        Backtrack(0, new List<int>(), target);
        return result;
    }
}

The crucial detail is passing i back into the recursive call, not i + 1. In Subsets, the recursive call advances the index because each element appears at most once. Here, you pass i again — this allows the same element to be selected multiple times, which is exactly what the problem requires. The monotone-index invariant still holds: future calls can only pick elements at position i or later, which prevents [3, 2] from ever being generated.

Tracing through the example

candidates = [2, 3, 6, 7], target = 7. After sorting: [2, 3, 6, 7].

The tree terminates at two valid leaves: [2, 2, 3] and [7]. Notice how the [3] subtree barely grows — once remaining drops to 1, every candidate (minimum 2) fails the > remaining check immediately and breaks. That's the pruning at work.

Step-by-step for the [2, 2, 3] path:

backtrack(start=0, current=[], remaining=7)
  pick candidates[0]=2 → current=[2], remaining=5
  backtrack(start=0, current=[2], remaining=5)
    pick candidates[0]=2 → current=[2,2], remaining=3
    backtrack(start=0, current=[2,2], remaining=3)
      pick candidates[0]=2 → current=[2,2,2], remaining=1
      backtrack(start=0, current=[2,2,2], remaining=1)
        candidates[0]=2 > 1 → break
      pop 2 → current=[2,2]
      pick candidates[1]=3 → current=[2,2,3], remaining=0
      backtrack(start=1, current=[2,2,3], remaining=0)
        remaining==0 → record [2,2,3]  ← FOUND
      pop 3 → current=[2,2]
      candidates[2]=6 > 3 → break
    pop 2 → current=[2]
    ...

The current[:] copy (Python) or new List<int>(current) (C#) at the leaf is non-negotiable. Without it, every entry in result would point to the same list, and you'd end up with all entries showing whatever the final state of current is after backtracking completes — likely empty.

Edge cases

No valid combination (candidates = [2], target = 1): candidates[0] = 2 > 1`, so the loop breaks immediately on the first call. Result is empty. The code handles this without any special case.

Single element equals target (candidates = [7], target = 7): candidates[0] = 7, remaining = 7. Equal, not greater, so you pick it. remaining - 7 = 0, base case fires, [7] is recorded. Correct.

All candidates exceed target (candidates = [5, 6, 7], target = 3): after sorting, candidates[0] = 5 > 3. The first loop iteration breaks. Empty result. Again, no special case needed — the pruning condition handles it.

Target divisible by minimum (candidates = [2, 3, 6, 7], target = 6): generates [2, 2, 2], [3, 3], and [6]. All three paths terminate correctly. The depth reaches 3 for [2, 2, 2] (the deepest path at 6/2=3 steps), which is well within the stack budget.

Complexity side by side

The asymptotic bound is the same in the worst case — you're still exploring a tree of depth T/M with up to N branches per node. But in practice the sorted version with pruning visits far fewer nodes. For the canonical example [2, 3, 6, 7] with target 7, the brute force explores paths starting [7, 2] and [6, 3] before realizing they overshoot, then also explores [2, 7] and [3, 6] as entirely separate paths. The sorted version never goes backward: once it picks 6 at depth 1 and sees remaining = 1 < 2, it breaks and skips 7 entirely. The constant factor savings are real, even if the big-O notation hides them.

Space: O(T/M) for the recursion depth, plus O(k * S) where k is the number of valid combinations and S is the average combination length — that's the output cost. You can't reduce the output cost; you have to store what the problem asks for.

Where this sits in the backtracking series

Subsets was the entry point: binary include/exclude, no constraints, no pruning. Combination Sum adds two things — a sum constraint and element reuse — and both of them flow naturally from the same backtracking skeleton. The start index does triple duty here: it prevents duplicates, it enables reuse (by passing i not i+1), and combined with sorting it enables early termination.

From here, the natural next problems are:

• Combination Sum II (LeetCode 40): same setup but each element can be used at most once, and the input may contain duplicates. The start index advances to i+1, and you add a skip guard: if candidates[i] == candidates[i-1] and i > start, skip to avoid duplicate combinations. One extra condition; same skeleton.
• Combination Sum III (LeetCode 216): find all combinations of exactly k numbers from 1 to 9 that sum to n. Two base cases instead of one — you check both count and sum. Prune early when count exceeds k.
• Word Search (LeetCode 79): backtracking in 2D space. Instead of a linear index controlling which elements you consider next, you use a visited grid. The undo step marks a cell unvisited. Same idea, different geometry.
• Letter Combinations of a Phone Number (LeetCode 17): at each position you pick one character from a fixed set. No reuse across positions, no sum constraint — but the skeleton is identical: loop over choices, recurse, undo.