Combination Sum

mediumBacktracking96 stepsJava · Python · C++

Find all combinations of candidates (each usable any number of times) that sum to target. Sort, then recurse with a remaining target. Passing the same index i again allows reuse; stopping when a candidate exceeds the remainder prunes the search.

▶ Watch the animated trace

Traced input: candidates = [2, 3, 6, 7], target = 7 → [[2, 2, 3], [7]]. Original problem: neetcode.io/problems/combination-target-sum

Complexity

BestO(2^(T/m))

Averageexponential

Worstexponential

SpaceO(T/m)

T = target, m = smallest candidate (bounds the depth).

Key idea

Recurse with i (not i + 1) to allow picking the same number again.
Starting each loop at start keeps combinations in non-decreasing order, so no duplicates.
After sorting, once a candidate is too big, every later one is too, so break.

Common mistakes

Recursing with i + 1 forbids reuse.
Looping from 0 produces [2, 3, 2] and [3, 2, 2] as different results.

Solution

Java

List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> res = new ArrayList<>();
    search(candidates, 0, target, new ArrayList<>(), res);
    return res;
}

void search(int[] c, int start, int remain, List<Integer> path, List<List<Integer>> res) {
    if (remain == 0) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < c.length; i++) {
        if (c[i] > remain) {
            break;
        }
        path.add(c[i]);
        search(c, i, remain - c[i], path, res);
        path.remove(path.size() - 1);
    }
}

Python

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    res = []

    def search(start: int, remain: int, path: List[int]) -> None:
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                break
            path.append(candidates[i])
            search(i, remain - candidates[i], path)
            path.pop()

    search(0, target, [])
    return res

C++

void search(vector<int>& c, int start, int remain, vector<int>& path, vector<vector<int>>& res) {
    if (remain == 0) {
        res.push_back(path);
        return;
    }
    for (int i = start; i < (int)c.size(); i++) {
        if (c[i] > remain) {
            break;
        }
        path.push_back(c[i]);
        search(c, i, remain - c[i], path, res);
        path.pop_back();
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> res;
    vector<int> path;
    search(candidates, 0, target, path, res);
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
No solution 2 is already too big.	`candidates = [2], target = 1`	`[]`
Reuse needed 2 is used four times in the first answer.	`candidates = [2, 3, 5], target = 8`	`[[2, 2, 2, 2], [2, 3, 3], [3, 5]]`
Target equals a candidate One element.	`candidates = [1], target = 1`	`[[1]]`