All Combinations That Sum to a Target With Repetition

medium backtracking combinations

Problem

Given an array of distinct positive candidates and a target, return every unique combination (multiset) where the chosen numbers sum to the target. Each candidate may be used unlimited 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;
}

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