39. Combination Sum (Medium)

Problem

Given an array of distinct positive integers candidates and a target integer, return all unique combinations where the chosen numbers sum to target. You may use each candidate unlimited times. Combinations are unique if the multiset of numbers chosen is unique; order doesn’t matter.

Example

candidates = [2,3,6,7], target = 7 → [[2,2,3], [7]]
candidates = [2,3,5], target = 8 → [[2,2,2,2], [2,3,3], [3,5]]

LeetCode 39 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, try all orderings, dedup

Recurse over every candidate (any number of times), deduplicate at the end by sorting each combination into a canonical form.

def combination_sum(candidates, target):
    found = set()
    def rec(remaining, path):
        if remaining == 0:
            found.add(tuple(sorted(path)))
            return
        if remaining < 0:
            return
        for c in candidates:
            path.append(c)
            rec(remaining - c, path)
            path.pop()
    rec(target, [])
    return [list(t) for t in found]

Complexity

Time: Exponential, every ordered sequence is explored, then collapsed.
Space: Same.

Wasteful; every combination is re-found under every permutation.

Swift

final class Solution {
    private func normalized(_ values: [[Int]]) -> [[Int]] {
        values.sorted { $0.lexicographicallyPrecedes($1) }
    }

    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        var unique = Set<[Int]>()
        func search(_ remaining: Int, _ current: [Int]) { if remaining == 0 { unique.insert(current.sorted()); return }; if remaining < 0 { return }; for value in candidates { search(remaining - value, current + [value]) } }
        search(target, []); return normalized(Array(unique))
    }
}

Approach 2: Backtracking with `start` index (canonical)

Enforce an ordering: once you “use” index i, later recursive calls can only consider indices ≥ i. This guarantees each combination is built in sorted candidate order exactly once.

Because we can reuse the same candidate, we pass i (not i + 1) when recursing after including.

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

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])     # L1: O(k) copy at leaf
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])           # L2: O(1) push
            backtrack(i, remaining - candidates[i])   # L3: recurse (reuse allowed)
            path.pop()                           # L4: O(1) pop

    backtrack(0, target)
    return result

function combinationSum(candidates: number[], target: number): number[][] {
    const result: number[][] = [];
    const path: number[] = [];

    function backtrack(start: number, remaining: number): void {
        if (remaining === 0) {
            result.push([...path]);     // L1: O(k) copy at leaf
            return;
        }
        if (remaining < 0) return;
        for (let i = start; i < candidates.length; i++) {
            path.push(candidates[i]);                       // L2: O(1) push
            backtrack(i, remaining - candidates[i]);        // L3: recurse (reuse allowed)
            path.pop();                                     // L4: O(1) pop
        }
    }

    backtrack(0, target);
    return result;
}

func combinationSum(candidates []int, target int) [][]int {
    result := [][]int{}
    path := []int{}

    var backtrack func(start, remaining int)
    backtrack = func(start, remaining int) {
        if remaining == 0 {
            cp := make([]int, len(path))
            copy(cp, path)
            result = append(result, cp) // L1: O(k) copy at leaf
            return
        }
        if remaining < 0 {
            return
        }
        for i := start; i < len(candidates); i++ {
            path = append(path, candidates[i])        // L2: O(1) push
            backtrack(i, remaining-candidates[i])     // L3: recurse (reuse allowed)
            path = path[:len(path)-1]                 // L4: O(1) pop
        }
    }

    backtrack(0, target)
    return result
}

Where the time goes, line by line

Variables: n = len(candidates), k = solution length (target / min(candidates)).

Line	Per-call cost	Times executed	Contribution
L1 (copy path)	$O(k)$	one per solution	$O(solutions · k)$
L2/L4 (push/pop)	$O(1)$	one per node	$O(tree nodes)$
L3 (recurse)	$O(1)$ dispatch	tree nodes	$O(n^k)$ ← dominates

The recursion tree has branching factor n and maximum depth k = target / min(candidates). The number of nodes is bounded by $O(n^k)$ .

Complexity

Time: Exponential in the depth of the search tree, bounded by $O(n^{target/min(candidates})$ ).
Space: $O(k)$ recursion, where k = target / min(candidates).

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    private func normalized(_ values: [[Int]]) -> [[Int]] {
        values.sorted { $0.lexicographicallyPrecedes($1) }
    }

    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        let values = candidates.sorted(); var result: [[Int]] = []
        func search(_ start: Int, _ remaining: Int, _ current: [Int]) { if remaining == 0 { result.append(current); return }; for index in start..<values.count where values[index] <= remaining { search(index, remaining - values[index], current + [values[index]]) } }
        search(0, target, []); return normalized(result)
    }
}

Approach 3: Sort + early termination (optimization)

Sort candidates ascending. When iterating, break the loop as soon as candidates[i] > remaining, every subsequent candidate is too large.

def combination_sum(candidates, target):
    candidates.sort()                  # L1: O(n log n) sort once
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])     # L2: O(k) copy at leaf
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                  # L3: O(1) prune entire suffix
            path.append(candidates[i])         # L4: O(1) push
            backtrack(i, remaining - candidates[i])  # L5: recurse
            path.pop()                         # L6: O(1) pop

    backtrack(0, target)
    return result

function combinationSum(candidates: number[], target: number): number[][] {
    candidates.sort((a, b) => a - b);   // L1: O(n log n) sort once
    const result: number[][] = [];
    const path: number[] = [];

    function backtrack(start: number, remaining: number): void {
        if (remaining === 0) {
            result.push([...path]);     // L2: O(k) copy at leaf
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break;    // L3: O(1) prune entire suffix
            path.push(candidates[i]);                // L4: O(1) push
            backtrack(i, remaining - candidates[i]); // L5: recurse
            path.pop();                              // L6: O(1) pop
        }
    }

    backtrack(0, target);
    return result;
}

func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates)              // L1: O(n log n) sort once
    result := [][]int{}
    path := []int{}

    var backtrack func(start, remaining int)
    backtrack = func(start, remaining int) {
        if remaining == 0 {
            cp := make([]int, len(path))
            copy(cp, path)
            result = append(result, cp) // L2: O(k) copy at leaf
            return
        }
        for i := start; i < len(candidates); i++ {
            if candidates[i] > remaining {
                break                               // L3: O(1) prune entire suffix
            }
            path = append(path, candidates[i])      // L4: O(1) push
            backtrack(i, remaining-candidates[i])   // L5: recurse
            path = path[:len(path)-1]               // L6: O(1) pop
        }
    }

    backtrack(0, target)
    return result
}

Where the time goes, line by line

Variables: n = len(candidates), k = solution length (target / min(candidates)).

Line	Per-call cost	Times executed	Contribution
L1 (sort)	$O(n log n)$	1	$O(n log n)$
L3 (prune)	$O(1)$	pruned nodes	$O(pruned)$
L5 (recurse)	$O(1)$ dispatch	surviving nodes	$O(n^k)$ worst ← dominates

Sorting enables L3 to cut entire subtrees. The asymptotic bound is the same, but the practical speedup on mixed-size inputs is substantial.

Complexity

Time: Same worst-case Big-O as Approach 2; practical speedup from pruning is substantial on inputs with mixed sizes.
Space: $O(k)$ recursion, where k = target / min(candidates).

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    private func normalized(_ values: [[Int]]) -> [[Int]] {
        values.sorted { $0.lexicographicallyPrecedes($1) }
    }

    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        let values = candidates.sorted(); var result: [[Int]] = []
        func search(_ start: Int, _ remaining: Int, _ current: [Int]) { if remaining == 0 { result.append(current); return }; for index in start..<values.count { let value = values[index]; if value > remaining { break }; search(index, remaining - value, current + [value]) } }
        search(0, target, []); return normalized(result)
    }
}

Summary

Approach	Time	Space
All orderings + dedup	huge	huge
Backtracking with `start`	$O(n^{target/min})$	$O(target/min)$
Sort + prune	same Big-O, faster in practice	same

The start index is the critical idea, same template solves Combination Sum II (40) and Subsets II (90) with a small tweak for duplicates.

Test cases

def combination_sum(candidates, target):
    candidates.sort()
    result = []
    path = []
    def backtrack(start, remaining):
        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

def _run_tests():
    r = combination_sum([2, 3, 6, 7], 7)
    assert sorted(map(tuple, r)) == sorted([tuple([2,2,3]), tuple([7])])
    r2 = combination_sum([2, 3, 5], 8)
    assert sorted(map(tuple, r2)) == sorted([tuple([2,2,2,2]), tuple([2,3,3]), tuple([3,5])])
    # single candidate
    assert combination_sum([3], 9) == [[3, 3, 3]]
    # no solution
    assert combination_sum([5], 3) == []
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function combinationSum(candidates: number[], target: number): number[][] {
    candidates.sort((a, b) => a - b);
    const result: number[][] = [];
    const path: number[] = [];
    function backtrack(start: number, remaining: number): void {
        if (remaining === 0) { result.push([...path]); return; }
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break;
            path.push(candidates[i]);
            backtrack(i, remaining - candidates[i]);
            path.pop();
        }
    }
    backtrack(0, target);
    return result;
}

const norm = (arr: number[][]): string =>
    JSON.stringify(arr.map(a => [...a].sort((x, y) => x - y)).sort((a, b) => JSON.stringify(a) < JSON.stringify(b) ? -1 : 1));

console.assert(norm(combinationSum([2, 3, 6, 7], 7)) === norm([[2,2,3],[7]]));
console.assert(norm(combinationSum([2, 3, 5], 8)) === norm([[2,2,2,2],[2,3,3],[3,5]]));
console.assert(norm(combinationSum([3], 9)) === norm([[3,3,3]]));
console.assert(combinationSum([5], 3).length === 0);
console.log("all tests pass");

func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    result := [][]int{}
    path := []int{}
    var backtrack func(start, remaining int)
    backtrack = func(start, remaining int) {
        if remaining == 0 {
            cp := make([]int, len(path))
            copy(cp, path)
            result = append(result, cp)
            return
        }
        for i := start; i < len(candidates); i++ {
            if candidates[i] > remaining { break }
            path = append(path, candidates[i])
            backtrack(i, remaining-candidates[i])
            path = path[:len(path)-1]
        }
    }
    backtrack(0, target)
    return result
}

Arrays, candidate list; sorted for pruning

Backtracking, search-tree tactics for exploring choices, undoing state, and pruning invalid branches.
Subsets and Combinations, choice-set tactics for generating selected groups while controlling duplicates and order.

39. Combination Sum (Medium)

Problem

Try it yourself

Approach 1: Brute force, try all orderings, dedup

Approach 2: Backtracking with start index (canonical)

Approach 3: Sort + early termination (optimization)

Summary

Test cases

Related data structures

Related concepts

Approach 2: Backtracking with `start` index (canonical)