40. Combination Sum II

At a Glance

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

Problem (one-liner)

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

Recognition Cues

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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.