Combination Sum IV
Count ordered sequences of given positive numbers that sum to target.
Why does this pattern fit?
Restate the exact job
Count ordered sequences of given positive numbers that sum to target.
Order matters, so every final choice extends all sequences for the remaining amount.
O(target·n) time · O(target) space
Looping numbers outside sums counts combinations, not ordered sequences.
How to solve Combination Sum IV
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Count ordered sequences of given positive numbers that sum to target.
Why Dynamic programming fits
Order matters, so every final choice extends all sequences for the remaining amount.
State to maintain
dp[sum] = number of ordered sequences totaling sum.
Transition
For sums from 1 to target, add dp[sum−number] for every usable number.
Time and space
O(target·n) time · O(target) space
Counterexample to the tempting mistake
Looping numbers outside sums counts combinations, not ordered sequences.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.