Combination Sum III
mediumTime: O(C(9,k) * k)Space: O(k)
Recognize the pattern
k numbers from 1-9 summing to nfixed count and targettiny search space
Brute force idea
All C(9,k) combinations — very small.
Better approach
Backtracking: choose from [start, 9], track remaining sum. Prune aggressively. O(C(9,k)).
Key invariant
The search space is at most C(9,k) — tiny. Aggressive pruning (sum > target, remaining digits < remaining slots) makes it extremely fast.
Watch out for
Not pruning — the search space is small enough that it works anyway, but pruning makes it instant.