Skip to main content

40. Combination Sum II

medium

Find every combination summing to a target when the candidates may contain duplicates and each candidate can be used at most once. The dedup-by-index pattern from Subsets II applied to a sum-target backtrack.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. Note: The solution set must not contain duplicate combinations.

Constraints

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

Examples

Example 1

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

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Sort candidates so duplicates are adjacent.

Hint 2

Each number can be used once, so the recursive call uses start = i + 1.

Hint 3

Dedup rule: at iteration index i > start, skip if candidates[i] == candidates[i-1]. The 'i > start' (not 'i > 0') matters — we still want the first copy at this depth.

Hint 4

Prune: break out of the loop once candidates[i] > remaining (because the array is sorted).

Solution approach

Reveal approach

Sort candidates ascending. Backtrack with (start, remaining, path). Base: remaining == 0 -> snapshot path. Recursive: for i from start while i < n and candidates[i] <= remaining: skip if i > start and candidates[i] == candidates[i-1] (this is the dedup); push candidates[i], recurse(i + 1, remaining - candidates[i], path), pop. Two important differences from Combination Sum: recursive call is i + 1 (each candidate used at most once), and the i > start dedup skip prevents duplicate combinations even though the input has duplicates. Time is O(2^n * n) worst case (every subset); the prune + dedup typically does far better. Space is O(target) recursion depth.

Complexity

Time
O(2^n * n)
Space
O(target)

Related patterns

  • backtracking
  • recursion
  • duplicates-handling

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg
  • Apple

Practice these live with InterviewChamp.AI

Drill Combination Sum II and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →