Skip to main content

39. Combination Sum

medium

Find every combination of candidate numbers that sums to a target, where each candidate may be used unlimited times. The cleanest 'reuse the same element' backtracking template — the one that finally clicks once Subsets and Permutations make sense.

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

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. The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

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]]

Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7.

Example 2

Input
candidates = [2,3,5], target = 8
Output
[[2,2,2,2],[2,3,3],[3,5]]

Example 3

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

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recurse with (start index, remaining target, path).

Hint 2

When remaining target hits 0, snapshot the path and return. When it goes negative, return without snapshotting.

Hint 3

Because the same element can be reused, the recursive call uses start = i, not i + 1.

Hint 4

Sorting + early break when candidates[i] > remaining gives a meaningful prune.

Solution approach

Reveal approach

Sort candidates ascending. Backtrack with (start, remaining, path). Base case: remaining == 0 -> snapshot path. Recursive case: for i from start while candidates[i] <= remaining: push candidates[i], recurse(i, remaining - candidates[i], path), pop. The crucial detail is the recursive call passes start = i (not i + 1) — this lets the same number be picked again at the next depth, which is what 'unlimited reuse' means. The 'i' (rather than 'start') is what enforces non-decreasing order in any single combination, which is what makes the unique-combination guarantee work. Sorting + the break on candidates[i] > remaining prunes most dead branches. Time is O(N^(T/M)) where N is candidates.length, T is target, M is the smallest candidate; space is O(T/M) recursion stack.

Complexity

Time
O(N^(T/M))
Space
O(T/M)

Related patterns

  • backtracking
  • recursion
  • unlimited-reuse

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Combination Sum and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →