LeetCode Combination Sum: Backtracking Template

Combination Sum (LeetCode 39, Medium) is the backtracking gateway problem. Master the start-index template here and a dozen other combinatorial problems become routine.

The Problem

Given a list of distinct positive integers candidates and a target integer target, return all unique combinations of candidates that sum to target. Each candidate may be reused unlimited times.

Example:

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

Brute Force

Generate every multiset up to target / min(candidates) length and filter those that sum to target. Exponential and not worth writing out.

Optimal Solution

Backtrack with a start index so each combination is generated in non-decreasing index order. Sort candidates to enable an early prune.

def combination_sum(candidates, target):
    candidates.sort()
    result = []

    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remaining:
                break
            path.append(c)
            backtrack(i, path, remaining - c)
            path.pop()

    backtrack(0, [], target)
    return result

Note backtrack(i, ...) not i + 1, because the same candidate can be reused.

Walk Through an Example

candidates = [2, 3, 6, 7], target = 7.

• Start with path [], remaining 7.
• Pick 2, path [2], remaining 5.
  • Pick 2, path [2,2], remaining 3.
    • Pick 2, path [2,2,2], remaining 1. Loop sees 2 > 1, break.
    • Pick 3, path [2,2,3], remaining 0. Record [2,2,3].
  • Pick 3, path [2,3], remaining 2. Loop sees 3 > 2, break.
• Pick 3, path [3], remaining 4.
  • 3 > ? Continue. Eventually no hit.
• Pick 7, path [7], remaining 0. Record [7].

Final: [[2,2,3],[7]].

Edge Cases

• Target less than smallest candidate: return empty list.
• Single candidate equal to target: returns one combination.
• Target zero: return [[]] if the problem allows it; LeetCode constraints typically exclude this.
• Large targets with small candidates: solution count can explode; the start-index trick prevents duplicate exploration but not exponential growth in valid combinations.

Complexity Analysis

• Time: O(N^(T/M)) in the worst case, where N is the candidate count, T is target, M is the smallest candidate. The branching factor is N, depth bounded by T/M.
• Space: O(T/M) for the recursion stack and current path; plus output size.

Backtracking complexity is hard to make tight; explain the bound and the pruning instead. See Big-O for context.

How to Explain It in an Interview

Open with the template: “I’ll use backtracking with a start index to avoid generating the same combination in different orders.” Explain why we pass i instead of i + 1: the problem allows reuse. Mention the sort + early break as a constant-factor improvement. Walk through one branch end-to-end; interviewers care about clean state management (push and pop in symmetry).

Related Problems

• LeetCode 40 Combination Sum II (each candidate used once, duplicates allowed in input)
• LeetCode 216 Combination Sum III
• LeetCode 78 Subsets
• LeetCode 46 Permutations

Wrap up

The start-index backtracking template is one of the highest-ROI patterns to internalize. Combination Sum is the cleanest demo: distinct candidates, reusable, fixed target. Once you can write this in under three minutes, the rest of the combinatorial set is just variations on the loop condition.