Skip to main content

44. Combination Sum

mediumAsked at Plaid

Find all unique combinations of candidates that sum to a target, where the same number may be chosen unlimited times. Plaid asks this because finding all ways to assemble a target balance from a fixed denomination set is the same primitive.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid backtracking screen.
  • LeetCode Discuss (2026)— Plaid SWE II OA.

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. Enumerate all subsets, filter by sum

Generate every possible multiset.

Time
exponential, no pruning
Space
O(target/min * count)
// Brute force — too slow without pruning.

Tradeoff: TLE without pruning.

2. Backtracking with start-index

DFS. At each step pick a candidate >= start-index (allows reuse but prevents permutation duplicates). Stop when sum hits target or exceeds it.

Time
O(n^(target/min))
Space
O(target/min)
function combinationSum(candidates, target) {
  const out = [];
  function bt(start, remaining, path) {
    if (remaining === 0) { out.push([...path]); return; }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) continue;
      path.push(candidates[i]);
      bt(i, remaining - candidates[i], path);
      path.pop();
    }
  }
  bt(0, target, []);
  return out;
}

Tradeoff: The start-index trick avoids permutation duplicates without a Set. Reusing the same candidate is enabled by passing i (not i+1) on the recursive call.

Plaid-specific tips

Plaid grades this on whether you avoid duplicates via the start-index trick rather than a Set. Bonus signal: explain why passing i (not i+1) allows reuse, and why starting from start (not 0) prevents [2,3] and [3,2] from both appearing.

Common mistakes

  • Passing i+1 instead of i in the recursive call — disallows reuse.
  • Starting the inner loop at 0 instead of start — produces duplicate permutations.
  • Forgetting to slice/clone path before pushing — outputs reference to the same path.

Follow-up questions

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

  • Combination Sum II (LC 40) — each element used at most once, candidates may repeat.
  • Combination Sum III (LC 216) — fixed count k of distinct digits 1-9.
  • Coin change (LC 322) — count combos with min coins.

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

Start-index implicitly enforces a canonical order (non-decreasing indices), preventing the same combination via different paths. Set dedup works but costs more space.

Why pass i (not i+1) for reuse?

Passing i lets the next level reconsider the same candidate. Passing i+1 would force unique elements per combination.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →