410. Count Ordered Ways to Reach a Total
Given k values available in unlimited supply, count the SEQUENCES that add
up to t. Order matters, so 1 2 and 2 1 are different.
values 1 2 3, target 4 -> 7
1111 112 121 211 22 13 31
Problem #231 counts COMBINATIONS of coins, where 1 2 and 2 1 are the same
and the answer for this input would be 4. The two problems differ by one line,
and which line it is decides everything.
Counting sequences:
for total in 1..t:
for each value v:
dp[total] += dp[total - v]
Counting combinations:
for each value v:
for total in v..t:
dp[total] += dp[total - v]
Same two loops, swapped. With the total outermost, every value may follow any prefix, so orderings are distinguished. With the value outermost, each value is finished with before the next begins, so the values appear in a fixed order and each multiset is counted once.
Being able to say which nesting gives which is worth more than either answer, because interviewers ask for one and candidates write the other.
The count grows quickly, so the input guarantees it fits in a signed 64-bit integer.
Constraints - `1 ≤ k ≤ 100` - `1 ≤ t ≤ 1000` - `1 ≤ value ≤ 1000` - The values are distinct. - The answer fits in a signed 64-bit integer.
Input
The first line contains two integers k and t.
The second line contains k space-separated distinct positive values.
Output
Print how many ordered sequences of the given values sum to exactly t.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.