Combination Sum

Problem

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

Approach

Sort candidates, then backtrack. Start from the current index (not 0) to avoid duplicate combinations. Prune when the candidate exceeds the remaining target.

When to Use

Partition into target — "all combinations summing to T", "coin change enumerate", "ways to split a budget". Unlimited reuse variant; start from current index to avoid duplicate combos. See also: dp/coin_change.

Complexity

Time	O(2^target) (bounded by target / min(candidates))
Space	O(target / min(candidates)) (recursion depth)

Implementation

SolutionTestsChallenge

combination_sum

Combination Sum — find combinations that sum to target.

Problem

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

Approach

Sort candidates, then backtrack. Start from the current index (not 0) to avoid duplicate combinations. Prune when the candidate exceeds the remaining target.

When to use

Partition into target — "all combinations summing to T", "coin change enumerate", "ways to split a budget". Unlimited reuse variant; start from current index to avoid duplicate combos. See also: dp/coin_change.

Complexity

Time: O(2^target) (bounded by target / min(candidates)) Space: O(target / min(candidates)) (recursion depth)

combination_sum

combination_sum(
    candidates: Sequence[int], target: int
) -> list[list[int]]

Return all combinations of candidates that sum to target.

combination_sum([2, 3, 6, 7], 7) [[2, 2, 3], [7]]

Source code in src/algo/backtracking/combination_sum.py

def combination_sum(candidates: Sequence[int], target: int) -> list[list[int]]:
    """Return all combinations of *candidates* that sum to *target*.

    >>> combination_sum([2, 3, 6, 7], 7)
    [[2, 2, 3], [7]]
    """
    result: list[list[int]] = []
    sorted_cands = sorted(candidates)

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

    backtrack(0, [], target)
    return result

tests/backtracking/test_combination_sum.py

"""Tests for combination sum."""

from algo.backtracking.combination_sum import combination_sum


class TestCombinationSum:
    def test_basic(self) -> None:
        result = combination_sum([2, 3, 6, 7], 7)
        assert sorted(result) == [[2, 2, 3], [7]]

    def test_single_candidate(self) -> None:
        result = combination_sum([2], 4)
        assert result == [[2, 2]]

    def test_no_solution(self) -> None:
        assert combination_sum([3], 2) == []

    def test_target_zero(self) -> None:
        result = combination_sum([1, 2], 0)
        assert result == [[]]

    def test_multiple_combinations(self) -> None:
        result = combination_sum([2, 3, 5], 8)
        expected = [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
        assert sorted(result) == sorted(expected)

    def test_all_sums_match_target(self) -> None:
        result = combination_sum([1, 2, 3], 5)
        for combo in result:
            assert sum(combo) == 5

Implement it yourself

Run: just challenge backtracking combination_sum

Then implement the functions to make all tests pass. Use just study backtracking for watch mode.

Reveal Solution

combination_sum

Combination Sum — find combinations that sum to target.

Problem

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

Approach

Sort candidates, then backtrack. Start from the current index (not 0) to avoid duplicate combinations. Prune when the candidate exceeds the remaining target.

When to use

Partition into target — "all combinations summing to T", "coin change enumerate", "ways to split a budget". Unlimited reuse variant; start from current index to avoid duplicate combos. See also: dp/coin_change.

Complexity

Time: O(2^target) (bounded by target / min(candidates)) Space: O(target / min(candidates)) (recursion depth)

combination_sum

combination_sum(
    candidates: Sequence[int], target: int
) -> list[list[int]]

Return all combinations of candidates that sum to target.

combination_sum([2, 3, 6, 7], 7) [[2, 2, 3], [7]]

Source code in src/algo/backtracking/combination_sum.py

def combination_sum(candidates: Sequence[int], target: int) -> list[list[int]]:
    """Return all combinations of *candidates* that sum to *target*.

    >>> combination_sum([2, 3, 6, 7], 7)
    [[2, 2, 3], [7]]
    """
    result: list[list[int]] = []
    sorted_cands = sorted(candidates)

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

    backtrack(0, [], target)
    return result