44. Combination Sum

Q: Why does the start index prevent duplicates?

By requiring each recursive level to pick candidates at or after start, we fix the order. [2, 3] is generated; [3, 2] never is because once we move past 2 we can't come back.

Q: Why dfs(i, ...) instead of dfs(i+1, ...)?

i allows the same candidate to be reused on the next call. i+1 would force moving on, disallowing reuse.

mediumAsked at Salesforce

Find all unique combinations of candidates that sum to target (candidates can be reused). Salesforce uses this as the canonical backtracking-with-reuse problem.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

Glassdoor (2026-Q1)— Salesforce uses this to test 'avoid duplicates by index ordering' technique.
LeetCode Discuss (2025)— Common pairing with LC 40 (no reuse) to test the variation.

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
1 <= candidates[i] <= 200
All elements of candidates are distinct.
1 <= target <= 500

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

Backtrack picking any candidate; dedup with sorted-stringified combinations.

Time: O(huge)
Space: O(huge)

function combinationSum(candidates, target) {
  const result = [];
  const seen = new Set();
  function dfs(remaining, path) {
    if (remaining === 0) {
      const key = [...path].sort((a, b) => a - b).join(',');
      if (!seen.has(key)) { seen.add(key); result.push([...path].sort((a, b) => a - b)); }
      return;
    }
    for (const c of candidates) {
      if (c <= remaining) { path.push(c); dfs(remaining - c, path); path.pop(); }
    }
  }
  dfs(target, []);
  return result;
}

Tradeoff: Generates duplicates that must be dedup'd. Salesforce will push for the index-pinned version.

2. Backtracking with start index

Pass a start index. Each recursive level can pick candidates[i..end], including reusing the current index. No duplicates because order is fixed.

Time: O(2^target)
Space: O(target / min(candidates))

function combinationSum(candidates, target) {
  const result = [];
  function dfs(start, remaining, path) {
    if (remaining === 0) { result.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 result;
}

Tradeoff: The `dfs(i, ...)` (not i+1) allows reuse. The `start` parameter avoids producing duplicates by fixing a non-decreasing order on selections.

Salesforce-specific tips

Salesforce specifically grades the index-pinning trick — it prevents duplicates WITHOUT explicit dedup sets, which is the difference between O(2^n) and O(n!). Bonus signal: explain why `dfs(i, ...)` allows reuse but `dfs(i+1, ...)` doesn't — the former keeps the current index available next call.

Common mistakes

Using dfs(i+1, ...) — disallows reuse, gives wrong answer.
Using dfs(0, ...) — generates duplicates (e.g., [2,3] and [3,2]).
Not slicing path before pushing — all results end up identical (same array reference).

Follow-up questions

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

Combination Sum II (LC 40) — no reuse, with duplicate candidates.
Combination Sum III (LC 216) — exactly k numbers from 1-9.
Combination Sum IV (LC 377) — count permutations, not 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 does the start index prevent duplicates?

By requiring each recursive level to pick candidates at or after start, we fix the order. [2, 3] is generated; [3, 2] never is because once we move past 2 we can't come back.

Why dfs(i, ...) instead of dfs(i+1, ...)?

i allows the same candidate to be reused on the next call. i+1 would force moving on, disallowing reuse.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →