Skip to main content

44. Combination Sum

mediumAsked at Workday

Find all unique combinations of candidates (reusable) summing to target. Workday uses this for backtracking with reuse — same shape as enumerating ways to allocate a fixed payroll budget across recurring expense categories.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

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.

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. Permutation-style backtracking with dedup set

Try every order, then dedup combinations by sorting.

Time
O(branching ^ depth)
Space
O(combinations)
// generates duplicates, dedups via JSON key — wasteful

Tradeoff: Wasteful — generates many sorted duplicates.

2. Backtracking with index-anchored start

At each level pass a 'start' index. Recurse with the SAME start to allow reuse, advance to skip.

Time
O(branching ^ depth)
Space
O(target / min(candidates))
function combinationSum(candidates, target) {
  const result = [];
  function backtrack(start, remaining, current) {
    if (remaining === 0) { result.push([...current]); return; }
    if (remaining < 0) return;
    for (let i = start; i < candidates.length; i++) {
      current.push(candidates[i]);
      backtrack(i, remaining - candidates[i], current);
      current.pop();
    }
  }
  backtrack(0, target, []);
  return result;
}

Tradeoff: The 'i' (not 'i+1') in the recursive call enables reuse. The 'start' guard prevents revisiting candidates in different orders.

Workday-specific tips

Workday wants the 'start index' pattern explained — it's how we ensure combinations are unique without sorting and deduping. Mention that reuse is enabled by recursing on i (not i+1).

Common mistakes

  • Recursing from 0 instead of start — generates [2,3] AND [3,2] as separate combinations.
  • Recursing from i+1 instead of i — forbids reuse.
  • Pushing current directly instead of a copy — all results share the same mutating array.

Follow-up questions

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

  • Combination Sum II (LC 40) — each candidate used at most once + duplicates in input.
  • Combination Sum III (LC 216) — exactly k numbers from 1-9.
  • Coin Change (LC 322) — minimum count instead of all combinations.

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 recurse on i instead of i+1?

Recursing on i means the same candidate can be picked again. Recursing on i+1 enforces single-use (LC 40 behavior).

Why pass start?

Without start, you'd generate [2,3] and [3,2] as separate paths. Start forces an ordering on combinations, deduping for free.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →