Skip to main content

45. Combination Sum II

mediumAsked at Snowflake

Find all unique combinations summing to target where each number can be used once, given an input that may contain duplicates. Snowflake asks this to test the sort-then-skip-equal pattern for dedup — same trick they use for DISTINCT over duplicate-laden columns.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake new-grad onsite paired with Combination Sum I.
  • LeetCode Discuss (2025-09)— Reported at Snowflake SDE-I screens.

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 + Set dedup

Backtrack picking distinct indices; collect into a Set of sorted-tuple strings.

Time
exponential + dedup
Space
exponential
// outline: backtrack with i+1 (no reuse), then dedup via Set of sorted-tuple keys.
// Works but does redundant exploration.

Tradeoff: Explores duplicates then dedups. Wasted CPU.

2. Sort + skip-equal-sibling (optimal)

Sort candidates. Recurse with start index; advance i+1 each call (no reuse). At each level, skip duplicate values to avoid emitting identical paths.

Time
exponential (but pruned)
Space
O(target) recursion
function combinationSum2(candidates, target) {
  candidates.sort((a, b) => a - b);
  const result = [];
  function dfs(start, path, remaining) {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
    if (remaining < 0) return;
    for (let i = start; i < candidates.length; i++) {
      if (i > start && candidates[i] === candidates[i - 1]) continue;
      if (candidates[i] > remaining) break;
      path.push(candidates[i]);
      dfs(i + 1, path, remaining - candidates[i]);
      path.pop();
    }
  }
  dfs(0, [], target);
  return result;
}

Tradeoff: Sort + skip-equal-sibling at the loop level enforces canonical traversal — no Set needed.

Snowflake-specific tips

Snowflake interviewers want the i > start && candidates[i] == candidates[i-1] dedup explained — at each recursion level, only the FIRST instance of a value is allowed; later equal values would generate identical paths. Bonus signal: connect to DISTINCT over duplicate-laden columns and how a sort-based DISTINCT exploits this same property.

Common mistakes

  • Skipping on i > 0 instead of i > start — overly aggressive, drops valid paths.
  • Forgetting to sort, making skip-equal logically impossible.
  • Recursing with i instead of i+1 — accidentally enables reuse.

Follow-up questions

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

  • Combination Sum III (LC 216).
  • Subsets II with duplicates (LC 90) — same skip-equal pattern.
  • How does sort-based DISTINCT work in Snowflake?

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 i > start (not i > 0)?

i > start ensures we only skip equal SIBLINGS at the current recursion level. i > 0 would also skip equal ancestors, which would drop valid combinations like [1,1,6].

How does sort enable dedup?

After sorting, equal values are adjacent. Skipping adjacent equals at each level guarantees we generate each unique combination exactly once.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →