Combination Sum

You are given an array candidates of distinct positive integers and a positive integer target. Return every unique combination of candidates whose values sum to target.

Each candidate may be used any number of times in a combination. Two combinations are the same if every value is used the same number of times in both, regardless of order, so [2, 3, 3] and [3, 2, 3] count once.

You may return the combinations in any order, and the numbers inside each combination in any order. If no combination works, return an empty list.

Example 1

Example 2

Example 3

Constraints

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All values in candidates are distinct.
• 1 <= target <= 40
• The number of valid combinations is less than 150.

Pattern Path · Backtracking · problem 119 of 169

Start simple

Generate every sequence of candidates up to the target and deduplicate them by sorting each one: exponential and wasteful because each combination is built in many orders.

The key idea

Search the tree of choices with backtracking. A state is the current partial combination plus the amount still remaining. When remaining hits 0, record a copy of the combination; when no candidate fits, return and undo the last choice.

The key detail is avoiding duplicate orderings. Generate every combination in non-decreasing index order: after picking candidates[i], the next pick may only come from index i onward. Staying at i allows reuse; never going back to a smaller index means [3, 2, 3] can never be produced once [2, 3, 3] has been. Each multiset therefore has exactly one path in the tree.

Sorting the candidates first gives a cheap prune: once candidates[i] > remaining, every later candidate is bigger too, so the loop can stop. The running time is proportional to the number of nodes explored, which is bounded by the size of the output times the target depth for inputs like these.

Complexity

• Time: O(N^(T/m)) in the worst case (N candidates, target T, smallest candidate m)
• Space: O(T/m) recursion depth besides the output

Python

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result, combo = [], []

        def backtrack(start: int, remaining: int) -> None:
            if remaining == 0:
                result.append(combo[:])  # store a copy
                return
            for i in range(start, len(candidates)):
                value = candidates[i]
                if value > remaining:
                    break  # sorted: every later candidate is too big as well
                combo.append(value)
                backtrack(i, remaining - value)  # i, not i + 1: reuse is allowed
                combo.pop()

        backtrack(0, target)
        return result

JavaScript

var combinationSum = function(candidates, target) {
  candidates.sort((a, b) => a - b);
  const result = [];
  const combo = [];

  const backtrack = (start, remaining) => {
    if (remaining === 0) {
      result.push([...combo]); // store a copy
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      const value = candidates[i];
      if (value > remaining) break; // sorted: every later candidate is too big
      combo.push(value);
      backtrack(i, remaining - value); // i, not i + 1: reuse is allowed
      combo.pop();
    }
  };

  backtrack(0, target);
  return result;
};

What the interviewer is checking

It tests whether you can write a clean backtracking template and, more importantly, control duplicates through the order of exploration rather than with a set afterwards.

Mistakes to avoid

• Restarting the loop from index 0 in each call, which produces every permutation of each combination.
• Passing i + 1 instead of i, which forbids reusing a candidate.
• Appending the shared list itself instead of a copy, so every result ends up empty.
• Breaking early on candidate > remaining without having sorted the candidates.

Follow-ups to expect

• What if each candidate can be used only once and candidates may repeat? (Skip equal neighbours, pass i + 1.)
• What if you only need the number of combinations? (Unbounded knapsack DP.)
• What if combinations must have exactly k numbers? (Add a length bound.)

In real software

Finding all ways to fill a budget or a container from item sizes, such as pack sizes that add up to an order quantity, uses this enumerate-with-reuse search.

Practice next