Combination Sum

You're given an array of distinct positive integers candidates and a positive integer target. Return every unique combination of candidates whose sum is exactly target.

You may use the same candidate any number of times. Two combinations are the same if they use each number the same number of times, so [2, 3, 3] and [3, 2, 3] count once.

Return the combinations in any order, and the numbers inside each combination in any order. If no combination works, return an empty list.

Building combinations one number at a time is a tree search: at each step pick a candidate, subtract it from the remaining target, and recurse. The question is how to avoid producing [2, 3, 3] and [3, 2, 3] as separate answers.

The fix is to only ever pick candidates in non-decreasing index order. Pass a start index into the recursion: you may choose candidates[start] again (reuse is allowed) or anything after it, but never anything before. Every multiset then has exactly one path to it.

Sorting the candidates first gives a free prune: once a candidate is bigger than what remains, every later one is too, so you can stop the loop.

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    candidates = sorted(candidates)
    results = []
    path = []

    def dfs(start, remaining):
        if remaining == 0:
            results.append(path[:])
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remaining:
                break
            path.append(c)
            dfs(i, remaining - c)  # i, not i + 1: reuse is allowed
            path.pop()

    dfs(0, target)
    return results

function combinationSum(candidates, target) {
  const sorted = [...candidates].sort((a, b) => a - b);
  const results = [];
  const path = [];

  const dfs = (start, remaining) => {
    if (remaining === 0) {
      results.push([...path]);
      return;
    }
    for (let i = start; i < sorted.length; i++) {
      const c = sorted[i];
      if (c > remaining) break;
      path.push(c);
      dfs(i, remaining - c); // i, not i + 1: reuse is allowed
      path.pop();
    }
  };

  dfs(0, target);
  return results;
}

Draw the first two levels of the decision tree and point out where duplicates would come from. Then introduce the start index as the rule that removes them. Interviewers want to hear "each combination is generated in sorted order, so exactly once."

Mention the sort-and-break prune and the "push, recurse, pop" structure out loud, since this template is reused in Combination Sum II, Subsets and Permutations.