39. Combination Sum

Quick Identifier

Topic: backtracking
Pattern: DFS / Backtracking
Difficulty: Medium
Companies: Amazon, Google, Meta, Microsoft, Bloomberg
Frequency: Very High
LeetCode: 39

Quick Sights

Time Complexity: O(2^target) from the optimal approach.
Space Complexity: O(recursion depth) excluding the final output unless stated.
Core Mechanism: Given distinct positive candidates and target, return all unique combinations that sum to target. The same number may be reused unlimited times.

Concept Explanation

Given distinct positive candidates and target, return all unique combinations that sum to target. The same number may be reused unlimited times.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

Sum exactly target with reuse
Combinations not permutations — enforce non-decreasing index order in DFS
Positive integers → bounded recursion

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute — generate multisets — exponential waste.
Optimal — DFS with start index, prune when sum > target — O(2^target) worst conceptual; tight in practice with pruning.

Optimal Solution

Go

func combinationSum(candidates []int, target int) [][]int {
	result := [][]int{}
	path := make([]int, 0, 16)

	var dfs func(start int, remaining int)
	dfs = func(start int, remaining int) {
		if remaining == 0 {
			copied := make([]int, len(path))
			copy(copied, path)
			result = append(result, copied)
			return
		}
		if remaining < 0 {
			return
		}
		for index := start; index < len(candidates); index++ {
			value := candidates[index]
			path = append(path, value)
			dfs(index, remaining-value)
			path = path[:len(path)-1]
		}
	}
	dfs(0, target)
	return result
}

JavaScript

function combinationSum(candidates, target) {
  const result = [];
  const path = [];

  function dfs(startIndex, remaining) {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
    if (remaining < 0) {
      return;
    }
    for (let index = startIndex; index < candidates.length; index += 1) {
      path.push(candidates[index]);
      dfs(index, remaining - candidates[index]);
      path.pop();
    }
  }

  dfs(0, target);
  return result;
}