Skip to main content

45. Combination Sum II

mediumAsked at Ola

Find all unique combinations summing to a target where each candidate is used at most once.

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

Problem

Given a collection of candidate numbers that may contain duplicates and a target, find all unique combinations where the candidate numbers sum to target. Each number may only be used once per combination.

Constraints

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

Examples

Example 1

Input
candidates = [10,1,2,7,6,1,5], target = 8
Output
[[1,1,6],[1,2,5],[1,7],[2,6]]

Example 2

Input
candidates = [2,5,2,1,2], target = 5
Output
[[1,2,2],[5]]

Approaches

1. Set of sorted tuples

Enumerate subsets and dedup via sorted-tuple strings.

Time
exp
Space
exp
// generate all subsets, filter sum=target, dedup with set of sorted joins

Tradeoff:

2. Sort and DFS skipping duplicates

Sort then DFS; at each level skip a candidate equal to its previous sibling.

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

Tradeoff:

Ola-specific tips

Ola interviewers care that you skip duplicates at the same DFS level; tie it to deduping combos of promo codes redeemed in one trip.

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 II 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 →