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
- Start with an empty combination and sum of 0
- At each number, decide: include it or skip it
- If current sum equals target: save this combination
- If current sum exceeds target: stop exploring this path (prune)
- 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.