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 Sam K., 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

More Recursion practice problems

See all Recursion problems →