Skip to main content

45. Combination Sum II

mediumAsked at Reddit

Find all unique combinations where each candidate is used at most once. Reddit uses this variant to test dedup with duplicates — the same skill needed when uniquifying overlapping abuse signals (each user-IP fingerprint appears at most once per detection batch).

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site question.

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]]

Approaches

1. Backtrack + filter dedup at end

Same as LC 39 with i+1, then dedup the result set.

Time
exponential
Space
exponential
// Anti-pattern: generates 2^n combos then dedups. Wastes time when most are duplicates.

Tradeoff: Memory-heavy and slow on dup-heavy inputs.

2. Sort + backtrack with sibling skip (optimal)

Sort candidates. In the loop at each level, skip i where candidates[i] == candidates[i-1] and i > start (same-level duplicate).

Time
O(2^n)
Space
O(n) recursion
function combinationSum2(candidates, target) {
  candidates.sort((a, b) => a - b);
  const out = [];
  function backtrack(start, current, remaining) {
    if (remaining === 0) { out.push([...current]); return; }
    for (let i = start; i < candidates.length; i++) {
      if (i > start && candidates[i] === candidates[i - 1]) continue;
      if (candidates[i] > remaining) break;
      current.push(candidates[i]);
      backtrack(i + 1, current, remaining - candidates[i]);
      current.pop();
    }
  }
  backtrack(0, [], target);
  return out;
}

Tradeoff: Single pass without post-dedup. The 'i > start' check is the critical guard.

Reddit-specific tips

Reddit interviewers explicitly check the 'i > start && candidates[i] === candidates[i-1]' guard. Bonus signal: explain why the i > start matters (we DO allow consuming consecutive duplicates within a combo — we just don't restart with a duplicate at the same level).

Common mistakes

  • Forgetting i > start (over-prunes and skips valid combos).
  • Forgetting to sort first.
  • Passing i instead of i + 1 (would re-use the same number).

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Combination Sum (LC 39) — with repetition.
  • Subsets II (LC 90) — same dedup pattern.
  • Permutations II (LC 47).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does i > start work?

At depth d, the first duplicate is fine; the second would produce the same combo. i > start means 'after the first sibling choice at this level'.

What's the early-break for?

Sorted candidates mean if candidates[i] > remaining, all later i are too big. Saves a lot.

Practice these live with InterviewChamp.AI

Drill Combination Sum II and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →