📖 10 min read
Last updated on

Combination Sum — Coding Interview Walkthrough

By intervu.dev

Hero Image for Combination Sum — Coding Interview Walkthrough

You’re in a coding interview. The interviewer gives you an array of distinct integers and a target, and asks you to find all unique combinations that sum to the target. Each number can be reused unlimited times. You know it’s backtracking, but the moment you start coding, three things go wrong simultaneously: duplicates appear, the undo step gets forgotten, and a reference sneaks in where a copy should be. Backtracking problems look simple on paper and fall apart under pressure.

This walkthrough covers how that conversation unfolds: the decision tree you should draw before writing a line of code, the choose/explore/unchoose pattern that structures every backtracking solution, and the specific bugs that catch even experienced candidates.

The Problem

Given an array of distinct positive integers candidates and a target integer target, return a list of all unique combinations of candidates that sum to target. The same number may be chosen from candidates an unlimited number of times. The solution set must not contain duplicate combinations.

(LeetCode #39)

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]]

In Example 1, there are exactly two ways to sum to 7 using elements from the array: picking 2 twice and 3 once, or picking 7 once. In Example 2, 2 can be reused four times, or combined with two 3s, or paired with 5. The order within each combination doesn’t matter: [2, 3, 3] and [3, 2, 3] are the same combination and should only appear once in the output.

Already comfortable with the solution? Practice it in a mock interview →

Decision tree for combination sum with candidates [2,3,6,7] and target 7. Three valid paths highlighted: [7], [2,2,3], [2,2,3].

What Interviewers Are Actually Testing

Combination Sum is a gateway backtracking problem. Interviewers use it to gauge whether you can structure a recursive search and reason about when to branch, when to prune, and how to avoid duplicates.

SkillWhat Interviewers Observe
Backtracking patternCan you build a recursive function that explores choices and undoes them cleanly?
Decision tree thinkingDo you draw out the search space before coding, rather than diving in blind?
Duplicate avoidanceDo you understand why starting each recursive call from the current index (not 0) prevents duplicates?
PruningDo you add the remaining < 0 early-exit check, and do you know how sorting enables stronger pruning?
Clean recursionIs your base case correct, your recursive call well-scoped, and your undo step explicit?

Step 1: Clarifying Questions

A few targeted questions before coding show you understand the problem’s constraints and aren’t just pattern-matching.

1. Can the same candidate be used more than once? Yes, the problem explicitly allows unlimited reuse. This directly affects the recursive call structure. If reuse weren’t allowed, you’d advance the index by 1 on each recursive call; since it is allowed, you stay at the same index.

2. Are the candidates guaranteed to be distinct? Yes for this problem. If duplicates were allowed in the input (as in Combination Sum II), you’d need a different deduplication strategy. Confirming the input is distinct keeps you on the right version.

3. Can the target be zero? Technically yes, the empty combination [] sums to zero. This is an edge case worth noting, though LeetCode constrains target to be at least 1.

4. Does the order of elements in each combination matter? No. [2, 3, 3] and [3, 2, 3] are considered the same combination. This reinforces why you need a strategy to avoid generating both orderings, which is exactly what fixing the start index solves.

5. Are all candidates positive? Yes. This matters because it means once your running sum exceeds the target, no further additions can bring it back down, enabling clean pruning.

Step 2: A First (Non-Optimal) Idea

The most natural first instinct is to generate all possible combinations and filter the ones that sum to the target.

from itertools import combinations_with_replacement

def combination_sum_brute(candidates, target):
    results = []
    for length in range(1, target + 1):
        for combo in combinations_with_replacement(candidates, length):
            if sum(combo) == target:
                results.append(list(combo))
    return results

This is correct for small inputs, but deeply inefficient. It generates an enormous number of combinations before checking sums, including many that clearly overshoot the target early on. More importantly, this approach doesn’t demonstrate the backtracking skill the interviewer is looking for. It outsources the search to a library function rather than building the recursive structure explicitly.

Step 3: The Key Insight

Model this as a decision tree. At each node, decide which candidate to include next, but only consider candidates at the current index or later. This prevents generating [2, 3] and [3, 2] as separate combinations. Recurse with the same index to allow reuse; subtract from the remaining target; record the combination when remaining hits zero; prune when it goes negative.

Draw the tree for candidates = [2, 3, 6, 7], target = 7:

start([], remaining=7)
├── pick 2 → ([2], remaining=5)
│   ├── pick 2 → ([2,2], remaining=3)
│   │   ├── pick 2 → ([2,2,2], remaining=1)
│   │   │   ├── pick 2 → remaining=-1 ✗ PRUNE
│   │   │   └── pick 3 → remaining=-2 ✗ PRUNE
│   │   └── pick 3 → ([2,2,3], remaining=0) ✓ ADD
│   └── pick 3 → ([2,3], remaining=2)
│       ├── pick 3 → remaining=-1 ✗ PRUNE
│       └── ...
└── pick 7 → ([7], remaining=0) ✓ ADD

Two things make this efficient:

1. Fix the start index. Each recursive call only considers candidates at the current index or later. This ensures [2, 3] and [3, 2] are never both generated.

2. Prune when remaining goes negative. Since all candidates are positive, if the remaining sum drops below zero, no path from here can reach zero. If you sort the candidates first, you can also break out of the loop the moment a candidate exceeds the remaining sum, skipping all larger candidates too.

Step 4: Optimal Strategy

  1. Sort candidates (enables early loop breaking during pruning).
  2. Define a recursive helper backtrack(start, current_combo, remaining).
  3. Base case (found): If remaining == 0, append a copy of current_combo to results and return.
  4. Base case (overshot): If remaining < 0, return immediately.
  5. Recursive step: Loop through candidates from index start to end:
    • If candidates[i] > remaining, break (all subsequent candidates are also too large).
    • Append candidates[i] to current_combo.
    • Recurse with backtrack(i, current_combo, remaining - candidates[i]). Pass i (not i+1) to allow reuse.
    • Remove candidates[i] from current_combo (the undo step).
  6. Call backtrack(0, [], target) to kick off the search.

Python Implementation

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    results = []
    candidates.sort()  # Sorting enables early break pruning

    def backtrack(start: int, current_combo: list[int], remaining: int):
        # Base case: exact match found
        if remaining == 0:
            results.append(list(current_combo))  # Append a copy, not the reference
            return

        for i in range(start, len(candidates)):
            # Since candidates are sorted, all further values will also exceed remaining
            if candidates[i] > remaining:
                break

            # Choose: add this candidate to the current combination
            current_combo.append(candidates[i])

            # Explore: recurse with same index i (allows reuse of candidates[i])
            backtrack(i, current_combo, remaining - candidates[i])

            # Unchoose: remove the candidate to restore state for the next iteration
            current_combo.pop()

    backtrack(0, [], target)
    return results

The three-step structure inside the loop, choose, explore, unchoose, is the canonical backtracking pattern. Naming it explicitly to an interviewer signals you understand the pattern, not just this specific problem.

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

  • backtrack(0, [], 7) → pick 2 → backtrack(0, [2], 5)
    • pick 2 → backtrack(0, [2,2], 3)
      • pick 2 → backtrack(0, [2,2,2], 1)
        • pick 2 → 2 > 1 → break
      • pick 3 → backtrack(1, [2,2,3], 0) → result: [2,2,3] ✓
      • pick 6 → 6 > 3 → break
    • pick 3 → backtrack(1, [2,3], 2)
      • pick 3 → 3 > 2 → break
    • pick 6 → 6 > 5 → break
  • pick 3 → backtrack(1, [3], 4)
    • pick 3 → backtrack(1, [3,3], 1)
      • pick 3 → 3 > 1 → break
    • pick 6 → 6 > 4 → break
  • pick 6 → backtrack(2, [6], 1)
    • pick 6 → 6 > 1 → break
  • pick 7 → backtrack(3, [7], 0) → result: [7] ✓

Final output: [[2, 2, 3], [7]] ✓

Time & Space Complexity

AspectComplexityExplanation
TimeO(n^(T/M))n = candidates length, T = target, M = smallest candidate
Space (call stack)O(T/M)Maximum recursion depth is target divided by the smallest candidate
Space (output)O(k × T/M)k = number of valid combinations, each up to length T/M

Time: The bound O(n^(T/M)) captures the worst-case branching factor (n choices at each level) and maximum depth (T/M levels). In practice, pruning makes the actual runtime significantly faster than this bound.

Space: The recursion depth is bounded by T/M. Each level of recursion uses O(1) additional space beyond the combination being built.

Common Interview Mistakes

  1. Passing i + 1 instead of i in the recursive call. This is the single most common bug. Using i + 1 means each candidate can only be used once, producing wrong results for cases like [2, 2, 2, 2]. The whole point of this problem is unlimited reuse: you stay at index i when recursing.

  2. Appending current_combo directly instead of a copy. Writing results.append(current_combo) appends a reference to the list, not a snapshot. As backtracking unwinds and modifies current_combo, every entry in results gets mutated. Always append list(current_combo) or current_combo[:].

  3. Forgetting the undo step. Backtracking requires explicitly undoing each choice before the next iteration. Forgetting current_combo.pop() means the list grows monotonically across recursive calls and produces completely wrong combinations.

  4. Starting the inner loop from 0 instead of start. Starting from 0 each time means you’ll generate both [2, 3] and [3, 2], duplicate combinations that differ only in order. The start parameter exists specifically to prevent this.

  5. Not sorting before pruning with break. The break optimization relies on the candidates being in ascending order. If you skip the sort, a smaller candidate appearing after a larger one would be incorrectly skipped.

  6. Trying to code before sketching the decision tree. Backtracking problems have many moving parts. Candidates who jump straight to code almost always get the index management or undo step wrong. Drawing even a two-level decision tree takes 90 seconds and prevents most bugs.

  7. Checking remaining < 0 instead of using > remaining in the loop guard. Separating the success case (== 0) from the pruning (candidates[i] > remaining with break) is cleaner and less error-prone.

What a Strong Candidate Sounds Like

“I’m going to model this as a decision tree. At each node, I decide which candidate to include next, but I only consider candidates at the current index or later. That prevents me from generating the same combination in different orders. I recurse with the same index to allow reuse of the current candidate, subtract from the remaining target, and if I hit zero I record the combination. If remaining goes negative I prune. The key structural move is the undo step after each recursive call: that’s what makes it backtracking rather than just recursion. I’ll sort the candidates first so I can break out of the loop early once a candidate exceeds the remaining target. Let me sketch the decision tree for the example before I write the code.”

This response shows: the candidate understands the pattern abstractly, not just this problem; they identified the three key design decisions (start index, same-index recursion, undo step) before coding.

Example Interview Dialogue

Interviewer: Why do you pass i instead of i + 1 to the recursive call?

Candidate: Because each candidate can be reused unlimited times. Passing i means the next recursive call can pick the same candidate again. Passing i + 1 would force each candidate to be used at most once, which is correct for Combination Sum II, but not here.

Interviewer: What changes if each candidate can only be used once?

Candidate: Two things. First, I pass i + 1 instead of i in the recursive call, so we never revisit the current candidate. Second, if the input has duplicates (which Combination Sum II does), I need to skip over duplicate candidates at the same recursion level to avoid generating identical combinations. That means sorting first and adding a check: if i > start and candidates[i] == candidates[i-1]: continue.

Interviewer: What if the input candidates could be very large and the target was also large?

Candidate: The recursion depth would blow up. In that case, I’d think about whether a bottom-up dynamic programming approach makes more sense: build a table of combinations that sum to each value from 1 to target. It avoids deep recursion and may be faster for dense inputs with large values, though it trades stack space for table space.

Combination Sum is the entry point to the backtracking family. These problems all share the choose/explore/unchoose structure but vary the constraints:

  • Combination Sum II (LeetCode #40). Same pattern but each candidate used once, with duplicate inputs. Adds a deduplication step.
  • Combination Sum III (LeetCode #216). Restricted to digits 1-9, fixed combination length.
  • Subsets (LeetCode #78). Pure backtracking to enumerate all subsets: the simplest version of this decision tree.
  • Permutations (LeetCode #46). Backtracking where order matters, contrasts with combination problems.
  • Combination Sum IV (LeetCode #377). Asks for count of ordered combinations, pivots to dynamic programming.

Practice This in a Mock Interview

Reading this explanation gives you the conceptual scaffolding: the decision tree, the choose/explore/unchoose pattern, the index management. But backtracking problems have a way of falling apart under interview pressure. The undo step gets forgotten. The index gets incremented when it shouldn’t. A copy becomes a reference. These aren’t conceptual failures: they’re execution failures that only practice under realistic conditions can fix.

The gap between “I understand backtracking” and “I implement it cleanly on the first try while talking through it” is wider than it looks on paper.

Start a mock interview for Combination Sum on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →