Course contentsShow
← Computer Science
Lesson 862 of 2,87220. Recursion Patterns and TechniquesFree lesson

Combination Sum Problems

Finding all combinations of numbers that sum to a target using backtracking with decision trees.

Combination Sum Problems

What you'll learn: How to find all unique combinations of numbers that add up to a target value using backtracking and decision trees.

The Core Idea

Imagine you have a set of coins and need to find every possible way to make exact change for a dollar. That's a combination sum problem! You're exploring all possible choices where each number can contribute to reaching your target sum.

The key insight: at each step, you face a binary decision — include this number in your current combination, or skip it. This creates a decision tree you explore using backtracking.

How the Decision Tree Works

Picture exploring paths in a tree:

  • Each node represents a partial sum and remaining choices
  • Left branch: "add this number to my combination"
  • Right branch: "skip this number, try the next one"

When you reach the target sum, you've found a valid combination! If you exceed the target, backtrack — that path is a dead end.

The Pattern

  1. Start with an empty combination and sum of 0
  2. At each number, decide: include it or skip it
  3. If current sum equals target: save this combination
  4. If current sum exceeds target: stop exploring this path (prune)
  5. Backtrack and try the next possibility

The beauty is that backtracking automatically explores all possibilities without generating invalid combinations upfront.

Example Scenario

Numbers: [2, 3, 5], Target: 8

Valid combinations: [2,2,2,2], [2,3,3], [3,5]

The decision tree prunes paths like [5,5] (exceeds 8) and backtracks to try other options.

Key Takeaway: Combination sum problems use backtracking with decision trees to systematically explore all ways numbers can sum to a target, pruning invalid paths early to avoid wasted work.