loading

39. Combination Sum — Step-by-Step Visualization

mediumLeetCode #39ArrayBacktracking

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. **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]]`

Algorithm Pattern

Recursive Backtracking with State Sharing

Key Idea

We explore two decisions at each step: include the current candidate (and stay on the same index to allow reuse) or exclude the current candidate (move to the next index). This systematic exploration covers all possible combinations.

Step-by-Step Approach

  1. Define a recursive function `dfs(index, currentCombination, currentTotal)`.
  2. Base Case 1: If `currentTotal == target`, add a copy of `currentCombination` to our results.
  3. Base Case 2: If `currentTotal > target` or `index` is out of bounds, stop this branch.
  4. Decision 1 (Include): Add `candidates[index]` to the combination and recurse into the same index (allowing reuse).
  5. Backtrack: Pop the candidate after the recursive call finishes.
  6. Decision 2 (Exclude): Recurse into the next index `index + 1` WITHOUT adding the current candidate.

Common Gotchas

  • Don't forget to pass a copy of the current combination when a match is found, otherwise it will be emptied by subsequent backtracking pops.
  • The order of decisions matters slightly for visualization, usually following a depth-first search order.

Related Problems

← All problems