Skip to main content

44. Combination Sum

mediumAsked at Reddit

Find all unique combinations of candidates that sum to target (with repetition). Reddit uses this to test backtracking — the same pattern they'd use to enumerate sets of moderation actions that combine to a desired outcome.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site backtracking question.

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. Generate all subsets and filter

Enumerate every subset (with repetition up to target/min(candidates)) and keep sum == target.

Time
exponential
Space
exponential
// Anti-pattern: massive enumeration. Mention only.

Tradeoff: TLE for target=40.

2. Backtracking with index (optimal)

Recurse with current index, current sum, current combo. At each step: skip (i++) or take (stay at i, sum += candidates[i]). Avoid duplicates by never going back to earlier indices.

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

Tradeoff: The 'pass i, not i+1' keeps the door open for repetition while preventing duplicate combos.

Reddit-specific tips

Reddit interviewers grade on the start-index trick (prevents duplicate combos). Bonus signal: sort candidates and prune when remaining < candidates[i] (early termination saves big in the worst case).

Common mistakes

  • Passing i + 1 in recursion (no repetition allowed) — gives LC 40 behavior.
  • Pushing current directly instead of [...current] (mutation leaks into the result).
  • Forgetting to pop after recursing (state corruption).

Follow-up questions

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

  • Combination Sum II (LC 40) — each candidate used at most once.
  • Combination Sum III (LC 216) — exactly k numbers.
  • Coin change (LC 322) — minimum count, DP.

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 backtrack instead of DP?

DP counts combinations efficiently but doesn't enumerate them. The problem wants the actual combos.

Why is the time complexity not n!?

Each recursive branch can only reach a tree of depth T/min(candidates). With pruning, the branching is much less.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →