Skip to main content

44. Combination Sum

mediumAsked at Datadog

Find all unique combinations of candidate integers that sum to target, with reuse allowed. Datadog asks this for the backtracking-with-reuse pattern — same shape as expanding multi-resolution rollup partitions.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite backtracking question.
  • LeetCode Discuss (2025-09)— Datadog tagged.

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. Backtracking allowing revisit + dedup with Set

Recurse without start-index tracking; dedup combinations via sorted-tuple Set.

Time
exponential + dedup cost
Space
exponential
// Recurse considering every candidate at every level; collect all paths summing to target; dedup via sorted-tuple Set.

Tradeoff: Generates lots of dupes; dedup at the end is wasteful. Datadog will fail this for missing the start-index trick.

2. Backtracking with start-index (optimal)

Each recursion call takes a start index. Only consider candidates from start onward (allows reuse but prevents permutations of the same combination).

Time
O(N^(T/M)) where M = min candidate
Space
O(T/M) recursion
function combinationSum(candidates, target) {
  const out = [];
  function dfs(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]);
      dfs(i, remaining - candidates[i], path);
      path.pop();
    }
  }
  dfs(0, target, []);
  return out;
}

Tradeoff: Start-index prevents revisiting earlier candidates (which would create permutations of the same combination). Pass i (not i+1) to allow reuse. Datadog-canonical pattern.

Datadog-specific tips

Datadog grades on the start-index trick. Articulate: 'Passing i allows reuse of candidates[i]; passing i+1 would forbid it.' Mention the sort-and-prune optimization (sort candidates; break early when candidates[i] > remaining) for tighter pruning.

Common mistakes

  • Passing i+1 instead of i — disallows reuse, gives wrong answer.
  • Forgetting to pop — corrupts the path across branches.
  • Pushing path directly without copy ([...path]) — final out has stale references.

Follow-up questions

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

  • Combination Sum II (LC 40) — no reuse, with duplicates in candidates.
  • Combination Sum III (LC 216) — fixed count of numbers, range 1-9.
  • Coin Change (LC 322) — sum-to-target with min count instead of enumeration.

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 start-index prevent permutations?

It enforces a canonical order: we only consider candidates in increasing index. [2,3] and [3,2] both end up as [2,3] because once you pick 3, you can't go back to 2.

Why pass i, not i+1?

Passing i allows the next recursion to pick the same candidate again — that's how reuse works. i+1 would advance past it.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →