40. Combination Sum II

Find all unique combinations in a candidate list that sum to a target, where each number may be used at most once. Sort first, then backtrack — advancing to i + 1 to enforce single-use and skipping duplicate siblings at the same depth to kill duplicate results.

● MediumBacktrackingSortingPruningTypeScript

PROBLEM What we're solving

Given a list of candidates (may contain duplicates) and a target integer, return all unique combinations where the chosen numbers sum to the target. Each candidate may only be used once per combination. For example, candidates = [10,1,2,7,6,1,5], target = 8 should return [[1,1,6],[1,2,5],[1,7],[2,6]] — four unique combos, despite the duplicate 1s in the input.

KEY IDEA Sort + skip duplicate siblings

Insight → sort the array so that duplicate values sit next to each other. When iterating siblings at a given depth, if candidates[i] === candidates[i-1] and i > start, this sibling would produce the exact same sub-tree as the previous sibling — skip it. The i > start guard preserves the first occurrence so we can still use each value in a child call. Advancing to i + 1 (not i) prevents reuse of the same index.

RECIPE Sort, backtrack, skip, prune

0 · Sort. candidates.sort() so duplicates are adjacent and so the array is monotone for the pruning step.
1 · Base case. If remaining === 0, snapshot the current path and return — we found a valid combination.
2 · Loop from start. Try each index i from start onward as the next element to include.
3 · Skip dup siblings. If i > start && candidates[i] === candidates[i-1], this choice is identical to one already explored at the same depth — skip to avoid duplicate results.
4 · Prune. Because the array is sorted, if candidates[i] > remaining, all future candidates are also too large — break.
5 · Recurse. Push candidates[i], call backtrack(i + 1, remaining - candidates[i], path) (note i + 1, not i), then pop.

Classic confusion → the sibling-skip guard is i > start, not i > 0. Using i > 0 incorrectly blocks using the same value in a child call (e.g., the two 1s in [1,1,6] are from the same sorted list but at different depths, which is legal).

COST Complexity & alternatives

Brute force (no pruning / dedup)

O(2ⁿ)

Explore every subset; slow and produces duplicates.

Sort + skip + prune

O(2ⁿ) worst, far fewer in practice

Pruning eliminates overbudget branches early; skip kills dup sub-trees.

Space is O(target / min) for the recursion depth (at most that many elements can fit). The sort is O(n log n) and typically dominates the useful work.

Pattern transfer → the same sort + skip-sibling trick appears in Subsets II (keep/skip choice at each index), Permutations II (used-flag + skip when candidates[i] === candidates[i-1] && !used[i-1]), and Palindrome Partitioning. Any backtracking problem with duplicates in the input reaches for this pattern.

RUN IT Sort, skip duplicates, prune over-budget branches

candidates =target =

step 0 / 51

STARTSorted: [1, 1, 2, 5, 6, 7, 10]. Target: 8. Starting backtrack from index 0.

1function combinationSum2(candidates: number[], target: number): number[][] {
2▶  candidates.sort((a, b) => a - b);
3▶  const result: number[][] = [];
4 
5  function backtrack(start: number, remaining: number, path: number[]): void {
6    if (remaining === 0) {
7      result.push([...path]);
8      return;
9    }
10    for (let i = start; i < candidates.length; i++) {
11      // Skip duplicate siblings at the same recursion depth
12      if (i > start && candidates[i] === candidates[i - 1]) continue;
13      // Prune: sorted array means further candidates only grow
14      if (candidates[i] > remaining) break;
15      path.push(candidates[i]);
16      backtrack(i + 1, remaining - candidates[i], path);
17      path.pop();
18    }
19  }
20 
21  backtrack(0, target, []);
22  return result;
23}

101122536475106

State

[]

path

remaining

depth

start

—

results

currently chosenskipped (duplicate sibling)pruned (over budget)combination found

slowfast

TYPESCRIPT The solution, annotated

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

  function backtrack(start: number, remaining: number, path: number[]): void {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      // Skip duplicate siblings at the same recursion depth
      if (i > start && candidates[i] === candidates[i - 1]) continue;
      // Prune: sorted array means further candidates only grow
      if (candidates[i] > remaining) break;
      path.push(candidates[i]);
      backtrack(i + 1, remaining - candidates[i], path);
      path.pop();
    }
  }

  backtrack(0, target, []);
  return result;
}

Reading it block by block

Line 2 — sort first.Sorting is the prerequisite for both the skip-sibling deduplication and the pruning break. Without it, duplicates would not be adjacent and we couldn't break early.

Lines 5–7 — base case. When remaining hits zero the current path sums exactly to target. We spread-copy the path before pushing because the same array is mutated throughout the recursion.

Lines 8–9 — sibling skip. i > start means this is not the first option at this depth. If it equals the previous option, the sub-tree it would produce is identical to one we just finished — skip it. The guard must be i > start, not i > 0, so that a parent call can still pick this value.

Line 11 — pruning break. Because the array is sorted, once candidates[i] > remaining, every subsequent candidate is also too large. A break (not continue) cuts the entire remaining loop.

Lines 12–15 — choose / recurse / unchoose. The standard backtracking triple: push the candidate, recurse with i + 1 (single-use — never revisit the same index), then pop to restore state for the next sibling.

Complexity → Time: O(2ⁿ) worst case (all subsets), but pruning and deduplication make the practical cost far lower. Space: O(target / min(candidates)) for the call stack depth.

INTERVIEWFollow-ups they'll ask

"What if each element can be reused?" Remove the sort-skip and recurse with i instead of i + 1 — that's Combination Sum I (LC 39).
"Return the count, not the combinations?" A DP approach (unbounded or 0/1 knapsack) counts combinations in O(n · target) time without enumerating them.
"What if target can't be reached?" The backtracker simply never hits the base case for that path; the result array stays empty or partial. No special handling needed.
"How do you prove no duplicate results?" Sorted input + skip-sibling means every value at a given depth is tried at most once, so two sibling sub-trees cannot produce the same set.
"Permutations II next?" Use a boolean used[] array and skip when candidates[i] === candidates[i-1] && !used[i-1] to handle duplicates in full-permutation context.

OPTIMAL Backtracking

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

  function backtrack(start: number, remaining: number, path: number[]): void {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      // Skip duplicate siblings at the same recursion depth
      if (i > start && candidates[i] === candidates[i - 1]) continue;
      // Prune: sorted array means further candidates only grow
      if (candidates[i] > remaining) break;
      path.push(candidates[i]);
      backtrack(i + 1, remaining - candidates[i], path);
      path.pop();
    }
  }

  backtrack(0, target, []);
  return result;
}

Complexity → Time: O(2ⁿ) worst case (all subsets), but pruning and deduplication make the practical cost far lower. Space: O(target / min(candidates)) for the call stack depth.

ALT 1 Brute force — enumerate every subset, filter, dedup

O(2^n · n) time · O(2^n · n) space

Each candidate is either in or out, so walk all 2^n subsets, keep the ones whose sum equals target, and drop duplicates by stringifying each sorted combination into a set.

approach-2.ts
function combinationSum2(candidates: number[], target: number): number[][] {
  const sorted = [...candidates].sort((a, b) => a - b);
  const seen = new Set<string>();
  const result: number[][] = [];

  function subsets(i: number, path: number[], sum: number): void {
    if (sum === target) {
      const key = path.join(',');   // path stays sorted as we go
      if (!seen.has(key)) {
        seen.add(key);
        result.push([...path]);
      }
      return;
    }
    if (i === sorted.length || sum > target) return;

    // Include candidate i (used once).
    path.push(sorted[i]);
    subsets(i + 1, path, sum + sorted[i]);
    path.pop();

    // Exclude candidate i.
    subsets(i + 1, path, sum);
  }

  subsets(0, [], 0);
  return result;
}

Note → This explores all 2^n subsets even when sums have already shot past target, and leans on a set to undo the duplicate combinations it generates. Pruning with if (candidates[i] > remaining) break and skipping equal siblings at the same depth (the optimal) avoids the wasted branches and the dedup set entirely.

MNEMONIC The one-liner

"Sort, start+1 prevents reuse, i>start skip kills the twin branch."

TRIGGERS When you see _ → reach for _

"combinations / subsets, no reuse, duplicates in input"	sort + backtrack(i+1) + skip-sibling
backtracking produces duplicate results	sort + if (i > start && arr[i] === arr[i-1]) continue
"all combinations that sum to target"	backtracking with remaining budget
large input, many duplicates	prune with break when candidates[i] > remaining

SKELETON The reusable shape

skeleton.ts
candidates.sort((a, b) => a - b);
const result: number[][] = [];

function backtrack(start: number, remaining: number, path: number[]): void {
  if (remaining === 0) { result.push([...path]); return; }
  for (let i = start; i < candidates.length; i++) {
    if (i > start && candidates[i] === candidates[i - 1]) continue; // skip dup siblings
    if (candidates[i] > remaining) break;                            // prune
    path.push(candidates[i]);
    backtrack(i + 1, remaining - candidates[i], path);
    path.pop();
  }
}
backtrack(0, target, []);
return result;

FLASHCARDS Tap to flip

Why sort before backtracking in Combination Sum II?

Sorted order groups duplicates together (enabling the skip) and makes the early-break pruning possible.

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For candidates = [10,1,2,7,6,1,5], target = 8, how many unique valid combinations exist?

QUESTION 02

Why must the guard for skipping duplicate siblings be i > start rather than i > 0?

QUESTION 03

After sorting, when can we use break instead of continue in the candidate loop?

QUESTION 04

What changes between Combination Sum I (LC 39) and Combination Sum II (LC 40)?

QUESTION 05

What is the worst-case time complexity of this backtracking solution?

QUESTION 06

candidates = [2,5,2,1,2], target = 5. After sorting, the array is [1,2,2,2,5]. How many sibling-skip events happen at the top depth (start=0)?

QUESTION 07

Why must we push a copy ([...path]) rather than the path array itself when recording a result?

QUESTION 08

#40 · Combination Sum IISort the candidates; each element can be used at most once (advance to i+1 at each level). Skip duplicate sibling candidates at the same depth to avoid duplicate combinations.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Sort + skip duplicate siblings

RECIPE Sort, backtrack, skip, prune

COST Complexity & alternatives

RUN IT Sort, skip duplicates, prune over-budget branches

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Backtracking

ALT 1 Brute force — enumerate every subset, filter, dedup

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _