Skip to main content

44. Combination Sum

mediumAsked at Vercel

Given candidates and a target, return all unique combinations that sum to target (numbers may repeat). Vercel asks this for the backtracking-with-start-index pattern — same shape as their unbounded resource-bundling search.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; dedup via start-index expected.
  • Blind (2026-Q1)— Listed in Vercel screen pool.

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. Backtracking without start index (produces duplicates)

Try every candidate at every step; collect duplicates.

Time
exponential, with duplicates
Space
O(target/min)
// Produces [2,2,3] AND [2,3,2] AND [3,2,2]. Mention as the wrong shape.

Tradeoff: Duplicates blow up the search.

2. Backtracking with start index (optimal)

Track 'start' — only consider candidates from this index onward. This forces non-decreasing combinations and dedup.

Time
O(N^(T/M)) where T is target and M is min candidate
Space
O(T/M)
function combinationSum(candidates, target) {
  const out = [];
  function dfs(start, remaining, path) {
    if (remaining === 0) { out.push([...path]); return; }
    if (remaining < 0) return;
    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      dfs(i, remaining - candidates[i], path);
      path.pop();
    }
  }
  dfs(0, target, []);
  return out;
}

Tradeoff: The 'i' (not 'i+1') in the recursive call allows reuse of the same candidate. The start index dedups combinations without sorting.

Vercel-specific tips

Vercel grades the start-index trick. Bonus signal: explaining that `dfs(i, ...)` (not `i+1`) allows reuse and that 'start' enforces non-decreasing order to dedup. Pruning by sorting candidates and exiting early when candidates[i] > remaining is a strong optimization to mention.

Common mistakes

  • Recursing with `i + 1` — disallows reuse; produces wrong results.
  • Forgetting to copy path on push — pushes a reference that gets mutated later.
  • Not handling remaining < 0 — wastes work.

Follow-up questions

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

  • Combination Sum II (LC 40) — each candidate used once.
  • Combination Sum III (LC 216) — fixed-size combination.
  • Combination Sum IV (LC 377) — count permutations (order matters).

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 start-index dedup?

By only considering candidates[i..n], we never pick a smaller-index candidate after a larger one. Every valid combination is generated in exactly one non-decreasing order, so duplicates are impossible.

Can I sort and prune?

Yes — sort candidates ascending, then break the inner loop when candidates[i] > remaining. Saves significant work on large targets.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →