Skip to main content

44. Combination Sum

mediumAsked at Snowflake

Find all unique combinations of candidates summing to target, with reuse allowed. Snowflake asks this to test backtracking + the 'start index' trick to avoid duplicate combinations — the same technique used to enumerate physical plans without revisiting equivalent shapes.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this to set up plan-enumeration.
  • LeetCode Discuss (2025-09)— Reported at Snowflake new-grad screens.

Problem

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Constraints

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All elements of candidates are distinct.
  • 1 <= target <= 40

Examples

Example 1

Input
candidates = [2,3,6,7], target = 7
Output
[[2,2,3],[7]]

Example 2

Input
candidates = [2,3,5], target = 8
Output
[[2,2,2,2],[2,3,3],[3,5]]

Approaches

1. Recurse with no start index (broken dedup)

At each step, choose any candidate (with replacement); collect when sum hits target.

Time
exponential
Space
exponential
// Without start index: [2,2,3] and [2,3,2] both get emitted.
// Need to dedup with a Set of sorted tuples — wasteful.

Tradeoff: Generates permutations. Have to dedup at the end. Wasteful.

2. Backtracking with start index (optimal)

Recurse with a start index; each call may pick the same index (reuse) but not earlier ones — guarantees combinations, not permutations.

Time
O(N^(target/min))
Space
O(target/min) recursion
function combinationSum(candidates, target) {
  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++) {
      path.push(candidates[i]);
      dfs(i, path, remaining - candidates[i]); // i, not i+1 — reuse allowed
      path.pop();
    }
  }
  dfs(0, [], target);
  return result;
}

Tradeoff: Start-index enforces canonical ordering of combinations — no dedup needed.

Snowflake-specific tips

Snowflake interviewers want the start-index trick stated up front and pruning via remaining < 0. Bonus signal: pivot to physical-plan enumeration — when the planner explores alternative plans, it enforces canonical orderings on equivalent subplans to avoid revisiting equivalent shapes (the analogous 'start-index' constraint).

Common mistakes

  • Recursing with i + 1 instead of i — accidentally disallows reuse.
  • Forgetting to push [...path] (a copy) instead of path itself — all results share the same mutated array.
  • Pruning only at the sum == target check, not at sum > target.

Follow-up questions

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

  • Combination Sum II (LC 40) — distinct candidates, no reuse, may have duplicates.
  • Combination Sum III (LC 216) — fixed length k.
  • How does the planner avoid revisiting equivalent subplans?

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 pass i (not i+1) to the recursive call?

Reuse is allowed. Passing i lets the next level pick the same candidate again, generating combinations like [2,2,3].

Why does start-index prevent duplicates?

It enforces non-decreasing index order in the path. So [2,3,2] cannot be generated because once you've moved past index 1 (the 3), you can't go back to index 0 (the 2).

Practice these live with InterviewChamp.AI

Drill Combination Sum 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 →