Combination Sum

medium backtracking combinations

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.

Sort candidates ascending. Recurse with the current start index and remaining target. At each step, iterate i = start..n-1: stop the loop when candidates[i] > remain (sorting makes this prune correct). Otherwise pick it, recurse with i (not i + 1) so it can be reused, then pop. Hit zero — emit the path.

Inputcandidates = [2, 3, 6, 7], target = 7

Output[2,2,3] [7]

2+2+3 = 7 (repeating 2). 7 alone. 6 alone leaves 1 — no valid completion.

candidates (distinct, comma-separated)

target

def combination_sum(candidates, target):
    candidates.sort()
    out, path = [], []
    def back(start, remain):
        if remain == 0:
            out.append(path.copy()); return
        for i in range(start, len(candidates)):
            if candidates[i] > remain: break
            path.append(candidates[i])
            back(i, remain - candidates[i])
            path.pop()
    back(0, target)
    return out

function combinationSum(candidates, target) {
  candidates.sort((a, b) => a - b);
  const out = [], path = [];
  function back(start, remain) {
    if (remain === 0) { out.push(path.slice()); return; }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remain) break;
      path.push(candidates[i]);
      back(i, remain - candidates[i]);
      path.pop();
    }
  }
  back(0, target);
  return out;
}

List<List<Integer>> out = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    back(candidates, 0, target);
    return out;
}
void back(int[] c, int start, int remain) {
    if (remain == 0) { out.add(new ArrayList<>(path)); return; }
    for (int i = start; i < c.length; i++) {
        if (c[i] > remain) break;
        path.add(c[i]);
        back(c, i, remain - c[i]);
        path.remove(path.size() - 1);
    }
}

vector<vector<int>> out;
vector<int> path;
void back(vector<int>& c, int start, int remain) {
    if (remain == 0) { out.push_back(path); return; }
    for (int i = start; i < (int)c.size(); i++) {
        if (c[i] > remain) break;
        path.push_back(c[i]);
        back(c, i, remain - c[i]);
        path.pop_back();
    }
}
vector<vector<int>> combinationSum(vector<int>& c, int target) {
    sort(c.begin(), c.end());
    back(c, 0, target);
    return out;
}

Explanation

We want every group of numbers that sums to target, and here the same number may be reused as many times as we like. The natural tool is backtracking: build a path step by step and unwind when a branch is done.

First we sort the candidates ascending. The function back(start, remain) tries each candidate from index start onward. The crucial detail is recursing with i (not i + 1): staying on the same index lets a number be picked again, which is exactly what "unlimited use" means.

When remain reaches 0, the current path sums to the target, so we save a copy. After exploring a choice we pop it and move on, which is the backtracking undo step.

Sorting also gives a clean prune: if candidates[i] > remain: break. Once a candidate alone is bigger than what remains, every later candidate is even bigger, so we stop the loop entirely.

Example: sorted [2,3,6,7], target 7. Pick 2, again 2, then 3 → [2,2,3] sums to 7. Another branch picks 7 alone. Picking 6 leaves 1, which no candidate can finish, so that branch dies. Result: [[2,2,3],[7]].

Time: O(2^T) worst case Space: O(target / min) recursion