39. Combination Sum

At a Glance

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

Problem (one-liner)

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

Recognition Cues

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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;
}