Masai Packers and Movers
MediumP3Coding
You must move exactly k units of weight. Each trip uses one truck that is completely full, so a trip carries exactly one truck's capacity caps[i]. Trips happen one after another, and a truck may make as many trips as you like. Two plans are different if their sequences of trucks differ (order matters).
Return the number of different plans that carry exactly k units in total, modulo 1_000_000_007. If there is none, return 0.
Example 1
- Input
- k = 4, caps = [1,2]
- Output
- 5
- Why
- 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 gives 5 plans.
Example 2
- Input
- k = 5, caps = [2,3]
- Output
- 2
- Why
- 2+3 and 3+2.
Example 3
- Input
- k = 1, caps = [1]
- Output
- 1
Constraints
- 1 <= k <= 10^4
- 1 <= caps.length <= 20
- 1 <= caps[i] <= 100
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 11. ⌘Enter runs, ⌘⇧Enter submits.