Combination Sum

Approach Summary

Backtrack with start index. Can reuse same element (don't advance start). Prune when sum exceeds target.

Full Solution & Approach

Unlimited reuse changes the backtracking guard: at each step you may pick the same index again, so recursion passes the current start index instead of start + 1. The helper tracks the running sum; when it equals the target, record the path; when it exceeds the target, prune. The key to avoiding duplicate combinations is the start index — an element can only be chosen at or after its position in the array, which prevents the same set in different orders. Iterate i from start to the end, add candidates[i], recurse with the same i (reuse allowed), then pop. Because the candidates are sorted in many solutions, an early break when candidates[i] exceeds the remaining target prunes the search space substantially, though it is not required for correctness.

The recursion tree is bounded by the target over the smallest coin — O(target^(n/min)) worst case, far less in practice with pruning. The path depth is at most target / min element — O(target / min) space.

Solution Code

Solution

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    res = []

    def backtrack(start: int, path: list[int], total: int) -> None:
        if total == target:
            res.append(path[:])
            return
        if total > target:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, total + candidates[i])
            path.pop()

    backtrack(0, [], 0)
    return res

function combinationSum(candidates, target) {
  const res = [];
  const path = [];
  function backtrack(start, total) {
    if (total === target) {
      res.push([...path]);
      return;
    }
    if (total > target) return;
    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      backtrack(i, total + candidates[i]);
      path.pop();
    }
  }
  backtrack(0, 0);
  return res;
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(candidates, target, 0, new ArrayList<>(), 0, res);
    return res;
}

private void backtrack(int[] candidates, int target, int start, List<Integer> path, int total, List<List<Integer>> res) {
    if (total == target) {
        res.add(new ArrayList<>(path));
        return;
    }
    if (total > target) return;
    for (int i = start; i < candidates.length; i++) {
        path.add(candidates[i]);
        backtrack(candidates, target, i, path, total + candidates[i], res);
        path.remove(path.size() - 1);
    }
}

vector<vector<int>> combinationSum(const vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> path;
    function<void(int,int)> backtrack = [&](int start, int total) {
        if (total == target) { res.push_back(path); return; }
        if (total > target) return;
        for (int i = start; i < (int)candidates.size(); i++) {
            path.push_back(candidates[i]);
            backtrack(i, total + candidates[i]);
            path.pop_back();
        }
    };
    backtrack(0, 0);
    return res;
}

Edge Cases to Watch

No combination reaches the target — return []
A single candidate that divides the target — repeated copies are valid
Target 0 — the empty combination, [[]]
Candidates larger than the target — skipped

How to Recognize This Pattern

Unbounded element selection
Sum to target

Complexity Analysis

Time Complexity

O(n^(T/M))

Space Complexity

O(T/M)