Ordered Coin Sequences
Medium1-D Dynamic Programming
Problem
A ticket machine accepts coins with the distinct values in parts, inserted one at a time. Return how many different insertion sequences add up to exactly target, modulo 1,000,000,007.
Order matters: inserting 1 then 2 is a different sequence from 2 then 1.
Example 1
- Input:
- parts = [1, 2, 3], target = 4
- Output:
- 7
1111, 112, 121, 211, 22, 13, 31.
Example 2
- Input:
- parts = [9], target = 3
- Output:
- 0
Constraints
- 1 ≤ parts.length ≤ 200
- 1 ≤ parts[i] ≤ 1000, all distinct
- 1 ≤ target ≤ 1000
Hint
Show the first hint
This is the multi-stride staircase in disguise: target is the top step and each coin is a stride.
Walkthrough
How to approach it
01Clarify before coding
- Does order matter? Yes, which is the difference from counting coin mixes.
- Is there a limit on how many times a coin is used? No.
- Why a modulo? Counts grow exponentially with target.
02Brute force
Recursively try every coin as the next insertion while the remainder stays ≥ 0, counting exact hits. Memoise on the remainder.
Cost: Without memo: exponential. With memo: O(target·k) time, O(target) space.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.