Combination Sum II

Examples

Input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
Output: [[1,1,6], [1,2,5], [1,7], [2,6]]

The two 1s in the input let [1,1,6] use both of them, but each combination is only listed once even though there are two different 1s to pick from.

Input: candidates = [2, 5, 2, 1, 2], target = 5
Output: [[1,2,2], [5]]

There are three 2s available, so [1,2,2] can use two of them - but it's still only listed once.

Constraints

• 1 <= candidates.length <= 100

• 1 <= candidates[i] <= 50

• 1 <= target <= 30

Approach

This is like the earlier combination-sum problem, except each position in the input can only contribute once instead of unlimited times, and repeated values in the input need special handling so you don't end up with the same combination twice.

Handling "use each position once" is straightforward: once you use candidates[i], the next pick has to come from position i + 1 onward, never i again.

The trickier part is the duplicate values. A brute-force fix is to search without worrying about duplicates and then remove repeat combinations from the results afterward, the same de-duplication trick used for Subsets II. The cleaner fix is to sort the candidates first, then, whenever you decide to skip a value at a given step, also skip any later value at that same step that's identical to it - so you never explore two branches that would build the exact same combination.

Solutions

Brute Force — Backtrack Then De-duplicate

Move forward through the (unsorted) list one position at a time, using each position at most once, and collect every combination that sums exactly to the target. Because the input can hold duplicate values at different positions, the same combination can be built more than once - so afterward, collapse duplicates by keying each result on its sorted, comma-joined values.

function combinationSum2(candidates, target) {
  const all = [];
  const current = [];

  function backtrack(start, remaining) {
    if (remaining === 0) {
      all.push([...current]);
      return;
    }
    if (remaining < 0) return;

    for (let i = start; i < candidates.length; i++) {
      current.push(candidates[i]);
      backtrack(i + 1, remaining - candidates[i]);
      current.pop();
    }
  }

  backtrack(0, target);

  const seen = new Set();
  const result = [];
  for (const combo of all) {
    const key = [...combo].sort((a, b) => a - b).join(",");
    if (!seen.has(key)) {
      seen.add(key);
      result.push(combo);
    }
  }

  return result;
}

Time: O(2^n * n) to generate combinations, plus O(2^n * n) to key and de-duplicate them · Space: O(2^n * n) for the raw combinations and the de-duplication set

Optimal — Sort and Skip Duplicate Branches

Sort the candidates so equal values sit next to each other. Move forward through the list one position at a time (never revisiting a used position), and at each step skip over a candidate if it's equal to the one right before it at this same step - only the first equal value gets tried, which is enough to cover every combination that uses that value. Stop a branch as soon as the remaining target hits zero or a candidate would overshoot it.

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

  function backtrack(start, remaining) {
    if (remaining === 0) {
      result.push([...current]);
      return;
    }

    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remaining) break; // sorted, so nothing further can work either

      if (i > start && sorted[i] === sorted[i - 1]) continue; // skip duplicate at this level

      current.push(sorted[i]);
      backtrack(i + 1, remaining - sorted[i]); // i + 1: this position can't be reused
      current.pop();
    }
  }

  backtrack(0, target);
  return result;
}

Time: O(2^n) worst case · Space: O(n) recursion depth, plus a sorted copy of the input