A promotions engine listed every way to spend a gift card of target cents from a catalog of distinct pack prices. The same pack can be bought more than once. The intern restarted every choice from index 0 and returned [2, 3] and [3, 2] as two plans. Accounting wanted unique bags of coins, not every ordering of the same bag.

Combination Sum wants unique combinations that add to a target. A number may be reused. An array of distinct positives is the catalog. Restarting from 0 uses that catalog and still emits permutations of one multiset.

This is an interview writeup, not a backtracking lecture. The backtracking post owns choose, recurse, and undo. Here we only care about the start index: stay to reuse this coin, advance to drop it.

The problem

Given an int[] candidates of distinct positive integers and an int target, return every unique combination whose values sum to target. The same candidate may appear more than once in one combination. Two combinations are the same if they use the same values with the same frequencies. Order inside a combination does not matter.

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]
candidates = [2],          target = 1  →  (empty)

Note: Counting how many ways to make an amount, with unlimited coins, is unbounded coin change — a table, not this list. This prompt asks for the combinations themselves.

Restarting from 0 dumps permutations

At every remaining amount, try every coin from index 0. When remain hits 0, sort the path and drop it in a Set. Correct after the set. [2, 3] and [3, 2] both land. You still walk the permutation tree of every bag.

List<List<Integer>> combinationSumFromZero(int[] candidates, int target) {
    Set<List<Integer>> unique = new HashSet<>();
    dump(target, new ArrayList<>(), candidates, unique);
    return new ArrayList<>(unique);
}

void dump(int remain, List<Integer> path, int[] c, Set<List<Integer>> unique) {
    if (remain == 0) {
        List<Integer> t = new ArrayList<>(path);
        Collections.sort(t);
        unique.add(t);
        return;
    }
    if (remain < 0) {
        return;
    }
    for (int i = 0; i < c.length; i++) {
        path.add(c[i]);
        dump(remain - c[i], path, c, unique);
        path.remove(path.size() - 1);
    }
}

At target = 7 with [2, 3] this is a rounding error. At a larger target you paid for every ordering so a set could collapse them: reuse by staying at this index; advance to refuse this coin.

Stay to reuse, advance to drop

State is (start, remain). For i from start to the end: append candidates[i], recurse with the same i and remain - candidates[i], then pop. Recursing at i is reuse. Recursing at i + 1 would be “this coin at most once.” When remain == 0, copy the path. When candidates[i] exceeds remain, skip that coin.

Walk [2, 3, 6, 7] toward 7. After two 2s, a 3 finishes [2, 2, 3]. You never build [3, 2, 2] because index 0 is behind you once you picked 3.

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

start=0 remain=7
  take 2  path=[2] remain=5 start=0
    take 2  path=[2,2] remain=3 start=0
      take 2  path=[2,2,2] remain=1   all coins > 1, skip
      take 3  path=[2,2,3] remain=0   record
    take 3  path=[2,3] remain=2 start=1   3 > 2, skip rest
  take 3  ...
  take 7  path=[7] remain=0   record

The Java is that walk:

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

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

Time is exponential in T / min — branching over remaining coins, depth bounded by target / min(candidates). Extra space is O(T / min) for the path and the call stack, besides the output.

Note: Recurse at i, not i + 1. i + 1 is a different prompt (each candidate at most once). out.add(path) aliases the live list; later pops empty every recorded bag.

What interviewers usually poke next

  • Each coin at most once, input may repeat. Combination Sum II: sort, recurse at i + 1, skip a duplicate at the same depth. Do not reuse this i.
  • Count the ways, do not list them. Unbounded coin change — a table on (index, remain), not this tree. The backtracking post already sent that job to knapsack.
  • Sort first, then break. After a sort, c[i] > remain means every later coin is also too big. Optional prune; uniqueness already comes from the start index.
  • Negative candidates. The remain check no longer terminates. This prompt promised positives; ask before you invent a visited bound.

You are done with this problem when you can say, out loud, why restarting from 0 emits [2, 3] and [3, 2], why staying at i is the reuse, and why the copy of path is what you store.