Combination Sum III
mediumTime: O(C(9,k) * k)Space: O(k)
Signals to notice
k numbers from 1-9 summing to nfixed count and targettiny search space
Brute force first
All C(9,k) combinations — very small.
The key insight
Backtracking: choose from [start, 9], track remaining sum. Prune aggressively. O(C(9,k)).
What must stay true
The search space is at most C(9,k) — tiny. Aggressive pruning (sum > target, remaining digits < remaining slots) makes it extremely fast.
Easy way to go wrong
Not pruning — the search space is small enough that it works anyway, but pruning makes it instant.