Combination Sum

PracticeNeetCode ↗LeetCode ↗

Given an array of distinct positive integers candidates and a target integer target, return all unique combinations where the chosen numbers sum to target. The same number may be reused any number of times.

Example

Key Pointers

• Because numbers can repeat, the "include this number" recursive call stays at the same index, not index + 1.
• Sorting candidates first lets you break out of the loop early once a candidate exceeds the remaining target — cheap pruning.
• Moving to i + 1 for the next candidate is what represents "done considering this number, move on" in the search.

Step-by-Step Analysis

1. Sort candidates to enable early pruning.
2. Define backtrack(start, remaining): if remaining == 0, record a copy of path.
3. Loop i from start to len(candidates): break if candidates[i] > remaining (sorted, so nothing later can fit either).
4. Otherwise append candidates[i], recurse with backtrack(i, remaining - candidates[i]) — same i, since reuse is allowed — then pop.
5. Call backtrack(0, target) and return the result.

Complexity

Time: O(2^target) worst case — Space: O(target) recursion depth

Code

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    result = []
    path = []

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

    backtrack(0, target)
    return result

Code Explanation

How the solution above works, piece by piece.

1. Sort the candidates so the loop can break as soon as one is too big: all later ones are bigger.
2. remaining == 0: the path adds up exactly, so save a copy.
3. Loop from start: combinations are built in non-decreasing order, which prevents the same set appearing twice in different orders.
4. backtrack(i, remaining - candidates[i]) passes i, not i + 1, because the same number may be used again (2 + 2 + 3).
5. path.pop() undoes the choice before trying the next candidate.

Visual Walkthrough

The recursion tree for candidates = [2, 3, 6, 7], target = 7:

Video Explanation

NeetCode — Combination Sum, Backtracking, LeetCode 39