LeetCode · #39

Combination Sum Solution

Given an array of distinct integers and a target, find all unique combinations where the chosen numbers sum to the target. Each number may be used unlimited times.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #39

🏗️

Pattern

Backtracking — combination with reuse

Given an array of distinct integers candidates and a target integer target, return all unique combinations of candidates that sum to target. The same number may be chosen an unlimited number of times. Two combinations are unique if the frequency of at least one number differs.

Example

 Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]]
// [2,2,3] sums to 7; [7] sums to 7. Both valid. 

Constraints

 • 1 ≤ candidates.length ≤ 30 • 2 ≤ candidates[i] ≤ 40 • All elements of candidates are distinct • 1 ≤ target ≤ 40  ← small target limits depth of recursion 

Section Two · Approach 1

Brute Force — Try All Multi-sets

Generate all non-decreasing sequences of candidates up to length target/min(candidates) and check if each sums to target. This is equivalent to an unconstrained DFS that does not prune when the running sum already exceeds the target.

Why it works

Any combination summing to target will be found by exhaustive enumeration. Since candidates can repeat, the space is all multi-sets over the candidate array bounded by the target.

Why we can do better

Problem: Without pruning, we keep building combinations even after the running sum already exceeds target. Pruning the branch the moment remaining < 0 eliminates entire subtrees. Additionally, starting the inner loop from the current index (not 0) prevents generating duplicates like [3,2] when [2,3] has already been explored.

Java — Brute Force (no pruning, duplicates possible)

 import java.util.*;
class Solution {
public List<List<Integer>> combinationSum(int[] c, int target) {
List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(c);
dfs(c, 0, target, new ArrayList<>(), res);
return res;
    }
private void dfs(int[] c, int start, int rem,
List<Integer> path, List<List<Integer>> res) {
if (rem == 0) { res.add(new ArrayList<>(path)); return; }
// no early return for rem < 0 — brute force explores all if (rem < 0) return;
for (int i = start; i < c.length; i++) {
            path.add(c[i]);
dfs(c, i, rem - c[i], path, res); // i not i+1 — reuse allowed
path.remove(path.size() - 1);
        }
    }
}

Python — Brute Force

 class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        res = []
def dfs(start: int, rem: int, path: list) -> None:
if rem == 0: res.append(path[:]); return if rem < 0: return for i in range(start, len(candidates)):
                path.append(candidates[i])
dfs(i, rem - candidates[i], path)
                path.pop()
dfs(0, target, [])
return res

Metric	Value
Time	O(2^(t/m)) where t = target, m = min candidate — exponential
Space	O(t/m) — max recursion depth

Section Three · Approach 2

Backtracking with Pruning — O(2^(t/m))

Sort the candidates so that once a candidate exceeds the remaining target, no further candidate can work. This prunes entire branches early. Starting the loop from i (not 0) prevents duplicate orderings.

💡 Mental model: Picture a vending machine where coins have different denominations. You want to make exact change for a specific amount. You start with the smallest coin and keep adding the same coin until you exceed the amount, then backtrack and try the next coin. You never go back to a smaller coin — once you've moved past it, you commit to larger denominations only. This prevents generating [3,2] after already finding [2,3].

Algorithm — Backtracking with sort + start index

Sort candidates to enable early termination.
State: start index (no element before start is reconsidered) and remaining sum.
Base case success: remaining == 0 → add copy of path to result.
Pruning: if candidates[i] > remaining, break — all subsequent candidates are larger (sorted).
Reuse: recurse with i (not i+1) to allow reusing the current candidate.

🎯 When to recognize this pattern:

Any "find all combinations that sum to X" problem.
The signals are: output is a list of lists, elements can be reused or have a limited use count, and duplicates must be avoided.
This is the base for LC 40 (Combination Sum II, no reuse + duplicates), LC 216 (Combination Sum III, fixed size k), and LC 377 (Combination Sum IV, count only).

Why start = i and not start = 0:

Starting from i means the next call can still pick the same candidate (allowing repeats), but can never pick an earlier candidate (preventing duplicates like [3,2] = [2,3]).
This single invariant eliminates all ordering duplicates without needing a de-duplication set.

Section Four · Trace

Visual Walkthrough

Trace for candidates = [2, 3, 6, 7], target = 7. Only branches that reach rem=0 produce results.

Combination Sum — Backtracking Tree (candidates sorted: [2,3,6,7], target=7)

Section Five · Implementation

Code — Java & Python

Java — Backtracking with pruning

 import java.util.*;
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // enable early break backtrack(candidates, 0, target, new ArrayList<>(), res);
return res;
    }
private void backtrack(int[] cands, int start, int rem,
List<Integer> path,
List<List<Integer>> res) {
if (rem == 0) {
            res.add(new ArrayList<>(path)); // copy — path is mutable return;
        }
for (int i = start; i < cands.length; i++) {
if (cands[i] > rem) break; // sorted → all larger too, prune
path.add(cands[i]);
backtrack(cands, i, rem - cands[i], path, res); // i not i+1: reuse allowed
path.remove(path.size() - 1); // backtrack
}
    }
}

Python — Backtracking with pruning

 class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        res = []
def backtrack(start: int, rem: int, path: list) -> None:
if rem == 0:
                res.append(path[:]) # snapshot return for i in range(start, len(candidates)):
if candidates[i] > rem:
break # sorted → safe to stop
path.append(candidates[i])
backtrack(i, rem - candidates[i], path) # i allows reuse
path.pop() # backtrack backtrack(0, target, [])
return res

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute force (no pruning)	O(n^(t/m))	O(t/m)	Many redundant paths, duplicate orderings
DP (count only)	O(n · t)	O(t)	Can count combinations but cannot enumerate them
Backtracking + pruning ← optimal	O(2^(t/m))	O(t/m)	Enumerates all solutions, prunes invalid branches immediately

Why not dynamic programming?:

DP works when you only need to count combinations or find the minimum number.
Here the output is the actual combinations themselves — you must enumerate them.
DP cannot recover the full list without reconstruction overhead equivalent to backtracking.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single candidate equals target	`[7], target=7`	Result: `[[7]]`. One element, base case fires immediately.
No valid combination	`[3,5], target=4`	Result: `[]`. All paths are pruned before reaching 0.
Minimum candidate = 2	`[2], target=1`	2 > 1, pruned at first iteration. Returns `[]`.
Target exactly divisible	`[2], target=8`	Only one path: [2,2,2,2]. Depth = target/min = 4.
Multiple paths possible	`[2,3,6,7], target=7`	Both [2,2,3] and [7] valid. Algorithm finds both.
Large candidate exceeds target	`[2,100], target=6`	100 > 6 is pruned immediately after sort. No wasted recursion.

⚠ Common Mistake: Calling backtrack(i + 1, ...) instead of backtrack(i, ...). Using i+1 means each candidate can only be used once, giving you LC 40 (Combination Sum II) behavior, not LC 39. The problem explicitly says "may be used unlimited times" — you must pass i to allow the same index to be chosen again on the next level.

← Back to Backtracking problems

LearningTree

LC 39 · Combination Sum — Solution & Explanation | DSA Guide