40. Combination Sum II

Quick Identifier

Topic: backtracking
Pattern: DFS / Backtracking
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Meta, Apple
Frequency: High
LeetCode: 40

Quick Sights

Time Complexity: index+1 from the optimal approach.
Space Complexity: continue from the optimal approach.
Core Mechanism: Each candidate used at most once. Input may contain duplicates; solutions must be unique sets (not multiset permutations).

Concept Explanation

Each candidate used at most once. Input may contain duplicates; solutions must be unique sets (not multiset permutations).

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

Same as 39 but no reuse and duplicate values in array
Sort + skip equal neighbors at the same depth to dedupe

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute — set of visited indices with hash of sorted tuple — heavy.
Optimal — sort, DFS with index+1 after choose, continue while same as previous at same start.

Optimal Solution

Go

import "sort"

func combinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	result := [][]int{}
	path := make([]int, 0, 16)

	var dfs func(start int, remaining int)
	dfs = func(start int, remaining int) {
		if remaining == 0 {
			copied := make([]int, len(path))
			copy(copied, path)
			result = append(result, copied)
			return
		}
		if remaining < 0 {
			return
		}
		for index := start; index < len(candidates); index++ {
			if index > start && candidates[index] == candidates[index-1] {
				continue
			}
			value := candidates[index]
			if value > remaining {
				break
			}
			path = append(path, value)
			dfs(index+1, remaining-value)
			path = path[:len(path)-1]
		}
	}
	dfs(0, target)
	return result
}

JavaScript

function combinationSum2(candidates, target) {
  candidates.sort((left, right) => left - right);
  const result = [];
  const path = [];

  function dfs(startIndex, remaining) {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
    if (remaining < 0) {
      return;
    }
    for (let index = startIndex; index < candidates.length; index += 1) {
      if (index > startIndex && candidates[index] === candidates[index - 1]) {
        continue;
      }
      const value = candidates[index];
      if (value > remaining) {
        break;
      }
      path.push(value);
      dfs(index + 1, remaining - value);
      path.pop();
    }
  }

  dfs(0, target);
  return result;
}

Walkthrough

[10,1,2,7,6,1,5], target=8 → after sort [1,1,2,5,6,7,10]. At first level pick first 1, deeper; when second 1 at same level with same start rule, skip duplicate at index > start check.

Invariant: Sorted order + same-level skip removes duplicate combinations while allowing two 1s in different positions when values repeat in input.

Edge Cases

All numbers larger than target
Many duplicates

Pitfalls

Skipping duplicate without sort — fails
Using index+1 from unsorted unique by value only — may still duplicate paths

Variants

Count combinations only — DP on sorted array
Limited supply per value — multi-set capacity

Mind-Map Tags

#backtracking #dedupe #sort #combination #target-sum