Ways to Sum
Problem statement
An automated packaging system packs boxes. Given an integer total, calculate the number of ways to achieve total as a sum of items with integer weights from $1$ to $k$ inclusive. Order does not matter: a multiset such as $[1, 1, 2]$ is counted once regardless of arrangement.
Implement:
def ways(total, k):
...
where total is the value to sum to and k is the maximum integer weight allowed. Because the answer can be very large, return it modulo $10^9 + 7$.
Constraints: $1 \le \text{total} \le 1000$, $1 \le k \le 100$.
Example 1: total = 8, k = 2. There are $5$ multisets of values in $\{1, 2\}$ that sum to $8$: $[1,1,1,1,1,1,1,1]$, $[1,1,1,1,1,1,2]$, $[1,1,1,1,2,2]$, $[1,1,2,2,2]$, $[2,2,2,2]$. The answer is $5$.
Example 2: total = 5, k = 3. Using values from $\{1, 2, 3\}$ there are $5$ ways. The answer is $5$.
Show hint
Which classic dynamic-programming problem counts the ways to reach an amount using unlimited copies of each allowed value?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.
Related free problems
- Consecutive Numbers SumMedium