Combination Sum [Medium] — Backtracking with Pruning (LC 39)

Problem Statement#

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the answer in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Example 1:

Input:  candidates = [2, 3, 6, 7],  target = 7
Output: [[2, 2, 3], [7]]

Example 2:

Input:  candidates = [2, 3, 5],  target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct
• 1 <= target <= 40

Why This Problem Matters#

Combination Sum is the canonical introduction to backtracking in every serious interview preparation curriculum — and for good reason. It is not about a clever formula or a hash-map trick. It is about learning to think in terms of a decision tree: at every position in the input, you make a binary choice, recurse into the consequences of that choice, then undo it (backtrack) and try the other branch.

That pattern — choose, recurse, undo — is the skeleton of solutions for a large family of problems: generating permutations and subsets, solving Sudoku, parsing grammars, and planning game-tree moves. If you truly internalize backtracking here, you will find those other problems dramatically easier.

From an interview perspective, Amazon, Apple, Google, and Meta use this problem to probe several things at once:

1. Can you recognize that the state space is a tree? Many candidates try to write a nested loop and get stuck.
2. Do you understand how to prevent duplicate combinations? The key is always passing a start index so you never look backward in the candidate list.
3. Can you prune the search tree? Sorting the candidates and breaking early when a candidate exceeds the remaining target can cut the search space significantly.
4. Can you correctly handle the "use unlimited times" constraint? The trick is staying at the same index when you recurse after choosing a candidate — not advancing past it.

Getting all four of those right in a clean, well-commented solution is what an offer-level response looks like.

The Backtracking Decision Tree Insight#

The central idea is to model the problem as a tree where:

• Each node represents the current state: which candidates we have chosen so far and what the remaining target is.
• Each edge represents the decision to include one candidate.
• A node is a solution when the remaining target reaches exactly 0.
• A node is pruned (dead end) when the remaining target drops below 0.

The tree has two key structural choices:

Choice 1 — Use the current candidate again (same index): When we include candidates[i], we recurse with start = i (not i + 1). This allows the same candidate to appear multiple times in a combination.

Choice 2 — Skip to the next candidate (advance index): When we move past candidates[i] without including it (by iterating i forward in the loop), we guarantee that earlier candidates are never revisited. This is what prevents duplicate combinations like [3, 2, 2] when [2, 2, 3] has already been recorded.

The loop structure for i in range(start, len(candidates)) encodes both choices simultaneously: each iteration of i represents starting a fresh branch from candidate i, and the recursive call with start=i allows that same candidate to be reused within that branch.

Why sorting enables pruning: If we sort candidates in ascending order, then once candidates[i] > remaining, every subsequent candidate in the loop is also larger than remaining (since the array is sorted). We can break out of the loop immediately instead of testing them all. This transforms the worst-case behavior from exploring every leaf to cutting off entire subtrees early.

Visual Dry Run (Decision Tree Trace)#

Let us trace candidates = [2, 3, 6, 7], target = 7 step by step.

After sorting: [2, 3, 6, 7] (already sorted).

dfs(remaining=7, start=0, path=[])
│
├── choose 2  → dfs(remaining=5, start=0, path=[2])
│   │
│   ├── choose 2  → dfs(remaining=3, start=0, path=[2,2])
│   │   │
│   │   ├── choose 2  → dfs(remaining=1, start=0, path=[2,2,2])
│   │   │   │
│   │   │   ├── choose 2  → remaining=-1  ✗ pruned (< 0)
│   │   │   ├── choose 3  → remaining=-2  ✗ pruned (< 0)
│   │   │   └── (loop breaks — all candidates > 1)
│   │   │
│   │   └── choose 3  → dfs(remaining=0, start=1, path=[2,2,3])
│   │           remaining=0  ✓  RECORD [2,2,3]
│   │
│   ├── choose 3  → dfs(remaining=2, start=1, path=[2,3])
│   │   │
│   │   ├── choose 3  → remaining=-1  ✗ pruned
│   │   └── (loop breaks)
│   │
│   └── choose 6  → remaining=-1  ✗ pruned (loop breaks)
│
├── choose 3  → dfs(remaining=4, start=1, path=[3])
│   │
│   ├── choose 3  → dfs(remaining=1, start=1, path=[3,3])
│   │   └── (3 > 1, loop breaks)  ✗ dead end
│   │
│   └── choose 6  → remaining=-2  ✗ pruned
│
├── choose 6  → dfs(remaining=1, start=2, path=[6])
│   └── (6 > 1, loop breaks)  ✗ dead end
│
└── choose 7  → dfs(remaining=0, start=3, path=[7])
        remaining=0  ✓  RECORD [7]
 
Final answer: [[2,2,3], [7]]

Key observations from the trace:

1. When we choose 2 and recurse with start=0, the first choice available is still 2 — that is how unlimited reuse is implemented.
2. When we choose 3 at the top level, start becomes 1. The candidate 2 (index 0) is no longer available. This prevents us from generating [3, 2, 2] which would duplicate [2, 2, 3].
3. Sorting lets the loop break as soon as a candidate exceeds remaining, avoiding wasted recursive calls.

Common Mistakes#

Mistake 1: Recursing with start = i + 1 instead of start = i#

This is the most frequent bug. When you recurse with i + 1, you are saying "after choosing candidates[i], the next pick must come from candidates[i+1] onward." That prevents reuse of the same candidate, turning this into a completely different problem (LC 40 Combination Sum II). For LC 39, you must pass start = i to allow repeating the same candidate.

Wrong: dfs(remaining - candidates[i], i + 1, path) Right: dfs(remaining - candidates[i], i, path)

Mistake 2: Not copying the path when recording a solution#

In Python, lists are mutable and passed by reference. If you do result.append(path) and then continue backtracking (mutating path), every entry in result will point to the same list — and all of them will reflect the final empty state of path. You must append a snapshot: result.append(path[:]) or result.append(list(path)). In JavaScript the spread operator [...cur] serves the same purpose.

Mistake 3: Checking remaining < 0 instead of breaking on sorted input#

A solution that checks if remaining < 0: return inside the loop is correct but suboptimal. If candidates are sorted, the moment candidates[i] > remaining, all subsequent candidates are also larger than remaining. Instead of returning from each recursive call individually, break out of the for-loop entirely. This prunes entire subtrees in one step instead of one node at a time.

Mistake 4: Forgetting to backtrack (omitting the pop)#

The entire correctness of backtracking depends on undoing your choice after the recursive call returns. Appending to path before the recursive call and omitting path.pop() afterward means path accumulates every candidate ever chosen and is never restored to its pre-choice state. Each branch of the tree is then contaminated by the choices made in sibling branches.

Mistake 5: Not sorting before the loop and trying to break early#

Attempting to prune with break on an unsorted array produces wrong results — you might break early and miss valid candidates that happen to come later in the original order. Always sort first if you intend to use early-exit break instead of continue.

Solutions#

Python#

from typing import List
 
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # Sort so we can prune: once candidates[i] > remaining, all later ones are too
        candidates.sort()
 
        result: List[List[int]] = []
 
        def backtrack(remaining: int, start: int, path: List[int]) -> None:
            # Base case: exact match — snapshot path and record it
            if remaining == 0:
                result.append(path[:])   # path[:] is a copy; we must NOT append the live list
                return
 
            for i in range(start, len(candidates)):
                # Pruning: candidates are sorted, so if this one is too large,
                # every subsequent candidate is also too large — safe to break
                if candidates[i] > remaining:
                    break
 
                # Choose: add candidates[i] to our current combination
                path.append(candidates[i])
 
                # Recurse: pass start=i (not i+1) to allow re-using candidates[i]
                backtrack(remaining - candidates[i], i, path)
 
                # Undo the choice (backtrack): restore path to its pre-choice state
                path.pop()
 
        backtrack(target, 0, [])
        return result

JavaScript#

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    // Sort ascending so we can prune when a candidate exceeds remaining target
    candidates.sort((a, b) => a - b);
 
    const result = [];
 
    /**
     * @param {number} remaining  - how much more we need to reach target
     * @param {number} start      - earliest index we are allowed to pick from
     * @param {number[]} current  - the combination built so far (mutated in place)
     */
    function backtrack(remaining, start, current) {
        // Base case: we've hit the target exactly — record a snapshot of current
        if (remaining === 0) {
            result.push([...current]);   // spread copies the array; do NOT push current directly
            return;
        }
 
        for (let i = start; i < candidates.length; i++) {
            // Pruning: array is sorted, so if candidates[i] > remaining, all
            // later candidates are also too large — exit the loop early
            if (candidates[i] > remaining) break;
 
            // Choose: include candidates[i] in the current combination
            current.push(candidates[i]);
 
            // Recurse with start=i (same index) to allow re-using candidates[i]
            backtrack(remaining - candidates[i], i, current);
 
            // Undo: remove candidates[i] to restore state before this choice
            current.pop();
        }
    }
 
    backtrack(target, 0, []);
    return result;
};

Complexity Analysis#

The O(n ^ (T/M)) bound is tight in the worst case — for example candidates = [1], target = T forces following one path all the way to depth T. In practice with larger candidates and pruning, the tree is far shallower and narrower.

Follow-up Questions#

Interviewers at Amazon and Apple routinely follow LC 39 with one or more of these variants to see if you understand what each constraint is actually doing.

LC 40 — Combination Sum II (candidates with duplicates, each used at most once)#

The change: candidates may contain duplicates, and each element may only be used once.

What breaks in LC 39's solution: Reusing the same element is now forbidden, so you must pass start = i + 1 in the recursive call. But now you have a new problem: if candidates contains multiple 2s and the target is 5, both 2s sitting at index 0 and index 1 would produce the same combination [2, 3]. You get duplicate results.

The fix: After sorting, skip over consecutive duplicates at the same level of the decision tree. Specifically, within the for-loop at a given call frame, if i > start and candidates[i] == candidates[i-1], skip i with continue. This ensures each distinct value is tried at most once per level, eliminating duplicate output without a seen-set.

# Key difference from LC 39: i+1 in recursion, and skip-duplicate guard
for i in range(start, len(candidates)):
    if i > start and candidates[i] == candidates[i - 1]:
        continue  # skip duplicate at this level
    path.append(candidates[i])
    backtrack(remaining - candidates[i], i + 1, path)  # i+1: each element used once
    path.pop()

LC 216 — Combination Sum III (exactly k numbers from 1–9)#

The change: No input array. You must find all combinations of exactly k distinct digits from 1 to 9 that sum to n. Each digit used at most once.

What changes in the approach: The candidate set is always [1, 2, 3, 4, 5, 6, 7, 8, 9] (implicit). You add two extra pruning conditions: stop when len(path) > k (too many digits) and stop when remaining < 0. Record when remaining == 0 AND len(path) == k simultaneously.

This teaches the skill of composing multiple pruning conditions — a length constraint on top of the sum constraint.

LC 377 — Combination Sum IV (count ordered sequences, not unique combinations)#

The change: Return the count of sequences (order matters) that sum to target. [1, 2] and [2, 1] are counted separately.

What changes in the approach: Because order matters, this is no longer a combination problem — it is a permutation counting problem. The backtracking approach from LC 39 (which uses a start index to prevent re-visiting earlier candidates) would miss ordered sequences. The correct approach is bottom-up dynamic programming:

dp[0] = 1            (one way to form sum 0: the empty sequence)
for t in range(1, target + 1):
    for num in candidates:
        if t >= num:
            dp[t] += dp[t - num]

dp[target] is the answer. This is O(target * n) time and O(target) space — dramatically better than any backtracking approach for this variant, because there is no need to enumerate every sequence.

The interview lesson: LC 39 asks you to list combinations (no order), so backtracking with a start index is right. LC 377 asks you to count sequences (with order), so DP iterating all candidates at every sum is right. Confusing the two is a common mistake.

This Pattern Solves#

The unifying theme is always the same: choose a candidate, recurse into its consequences, undo the choice. The constraints of each problem (reuse, uniqueness, ordering, validity) are expressed by what you pass to the recursive call and what check you use to record a solution.

Key Takeaways#

• LeetCode 39 — Combination Sum is a Medium asked at Amazon, Apple, and Microsoft; backtracking with pruning is the standard approach.
• Pass start = i (not i + 1) in the recursive call to allow unlimited reuse of the same candidate.
• Always append a copy: result.append(path[:]) not result.append(path) — appending the live list records a reference, not a snapshot.
• Sort candidates and break early when candidate > remaining — prunes the search tree significantly for large inputs.
• Time O(n^target/min) in the worst case (exponential with pruning); space O(target/min) for the recursion depth.
• The start index is the encoding of "no duplicates in one combination" — changing it to i + 1 gives LC 40 (Combination Sum II with unique elements per combination).
• For LC 40 (candidates with duplicates): sort, use i + 1, and skip candidates[i] == candidates[i-1] when i > start to avoid duplicate combinations.

Next: Problem 47 — Permutations II →