Combination Sum II

MediumBacktrackingArrayBacktracking

Problem

You are given a list of positive integers, possibly containing duplicates, and a target sum. Return every combination of numbers from the list that adds up exactly to the target, using each array position at most once. The output must not contain duplicate combinations, even though the input has repeated values.

Example. For candidates [10, 1, 2, 7, 6, 1, 5] and target 8, two of the valid combinations are [1, 1, 6] and [1, 7].

Key idea

This looks like Combination Sum, but the rules flip: each position may be used at most once, while duplicate values across positions make it easy to produce the same combination twice from different index choices. Sorting the candidates first turns both concerns into one index-walking rule.

After sorting, recurse by index: at each step, either take the current element and move strictly forward (never revisiting the same index, unlike Combination Sum) or skip it. The duplicate risk lives in the skip decision: if the current element equals the one before it, and that previous element was itself skipped at this recursion level, taking the current one would rebuild a combination already explored. So once a run of equal values is skipped, skip the whole run; only its first occurrence may start a "take" branch. Reduce the remaining target as you recurse, record a combination when it reaches zero, and stop a branch early once the sorted remaining candidates are all too large.

Solution

function combinationSum2(candidates: number[], target: number): number[][] {
  const sorted = [...candidates].sort((a, b) => a - b);
  const result: number[][] = [];
  const partial: number[] = [];

  function backtrack(index: number, remaining: number): void {
    if (remaining === 0) {
      result.push([...partial]);
      return;
    }
    if (index === sorted.length || sorted[index] > remaining) {
      // Sorted candidates only grow from here, so nothing further can fit either.
      return;
    }

    // Take the current element and move strictly forward, since each
    // position is usable at most once.
    partial.push(sorted[index]);
    backtrack(index + 1, remaining - sorted[index]);
    partial.pop();

    // Skip the current element, and skip the rest of this run of
    // duplicates so only the run's first occurrence can start a take.
    let next = index + 1;
    while (next < sorted.length && sorted[next] === sorted[index]) {
      next++;
    }
    backtrack(next, remaining);
  }

  backtrack(0, target);
  return result;
}

Complexity

  • Time: exponential in candidate count in the worst case, substantially cut by sorting plus the duplicate-skip and overshoot pruning.
  • Space: O(n). Recursion depth bounded by the candidate count.

Watch out for

  • The duplicate-skip check compares against the previous sibling at the same recursion level, not the previous array element; getting this wrong drops valid combinations or leaks duplicates.
  • Advance strictly past the current index when recursing, since each position contributes at most once.

Pattern

This is sorted-array backtracking for bounded, without-replacement selection with duplicate suppression via same-level skipping. The same skip-the-repeated-run trick reappears in Subsets II and other problems built over arrays with repeated values.

Related questions