Combination Sum

Difficulty: Medium Source: NeetCode

Problem

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 combinations 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], target = 4 Output: [[2, 2], [3], [2, 3]] — wait, [3] sums to 3 not 4. Correct: [[2, 2]]… Actually: [[2, 2], [2, 2]] — no. 2+2=4 and 3 alone is 3 not 4. Output: [[2, 2]]

Example 3: 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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Backtracking — exploring choices and undoing them when a path doesn’t lead to a solution
• Recursion — building combinations incrementally

1. Brute Force

Intuition

Generate all possible combinations of candidates (with repetition) up to some maximum length and check whether each one sums to target. The maximum number of elements in a valid combination is target // min(candidates). This is horribly inefficient but gets the point across.

Algorithm

1. Compute max_len = target // min(candidates).
2. Generate all combinations with repetition up to length max_len.
3. Filter those that sum exactly to target.
4. Deduplicate (since the same set in different orders counts once).

Solution

from itertools import combinations_with_replacement

def combinationSum_brute(candidates, target):
    result = set()
    max_len = target // min(candidates)
    for length in range(1, max_len + 1):
        for combo in combinations_with_replacement(sorted(candidates), length):
            if sum(combo) == target:
                result.add(combo)
    return [list(c) for c in result]


print(combinationSum_brute([2, 3, 6, 7], 7))  # [[2, 2, 3], [7]]
print(combinationSum_brute([2, 3, 5], 8))       # [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Complexity

• Time: O(n^(target/min)) — exponential in the worst case
• Space: O(target/min) — recursion depth

2. Backtracking

Intuition

Walk through the candidates array from left to right. At each position i, you can either keep using candidates[i] (recurse with the same i, subtracting its value from the remaining target) or move on to candidates[i+1]. If the remaining target hits 0 you’ve found a valid combination; if it goes negative you prune that branch. Because we always recurse starting from the current index or later, we never produce duplicate combinations.

Algorithm

1. Define backtrack(start, current, remaining).
2. If remaining == 0: append a copy of current to results and return.
3. If remaining < 0: return (prune).
4. For each index i from start to len(candidates) - 1:
   • Append candidates[i] to current.
   • Recurse with start = i (same element allowed again) and remaining - candidates[i].
   • Pop candidates[i] from current.

Solution

def combinationSum(candidates, target):
    result = []

    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(list(current))
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])  # i not i+1 — reuse allowed
            current.pop()

    backtrack(0, [], target)
    return result


print(combinationSum([2, 3, 6, 7], 7))  # [[2, 2, 3], [7]]
print(combinationSum([2, 3, 5], 8))      # [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
print(combinationSum([2], 1))            # []

Complexity

• Time: O(n^(target/min)) — in the worst case, explores deep trees; sorting + pruning helps in practice
• Space: O(target/min) — maximum recursion depth

Common Pitfalls

Passing i + 1 instead of i when recursing. Since each candidate can be reused unlimited times, you need to recurse with start = i, not start = i + 1. Using i + 1 would prevent reuse and miss combinations like [2, 2, 3].

Not making a copy when appending to results. result.append(current) stores a reference; always use result.append(list(current)).

Not pruning when remaining < 0. Without this check, you’d explore paths that can never reach the target. Sorting candidates first lets you add an early break instead of return for more aggressive pruning.