Skip to main content

44. Combination Sum

mediumAsked at Ola

Find all unique combinations of candidates that sum to a target.

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

Problem

Given an array of distinct candidate integers and a target, return a list of all unique combinations of candidates where the chosen numbers sum to target. The same number may be chosen unlimited times.

Constraints

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • 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. Generate all multisets

Enumerate every multiset of size up to target/min and filter by sum.

Time
exp
Space
exp
// brute multiset; intractable for target >> 10

Tradeoff:

2. DFS with start index

Backtrack; at each level use candidates from a starting index to avoid duplicate orderings.

Time
O(N^(T/M))
Space
O(T/M)
function combinationSum(c, t) {
  const out = [];
  c.sort((a,b)=>a-b);
  const dfs = (i, path, rem) => {
    if (rem === 0) { out.push([...path]); return; }
    for (let j = i; j < c.length; j++) {
      if (c[j] > rem) break;
      path.push(c[j]);
      dfs(j, path, rem - c[j]);
      path.pop();
    }
  };
  dfs(0, [], t);
  return out;
}

Tradeoff:

Ola-specific tips

Ola interviewers want clean DFS scaffolding; tie it to finding all combinations of incentive payouts that hit a target spend per driver.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →