Token Orders at the Turnstile
A turnstile accepts tokens worth the amounts listed in tokens, inserted one at a time, and it opens as soon as the inserted amounts add up to exactly fare. You have an unlimited supply of every token. Return how many different insertion sequences open the turnstile. Sequences that use the same tokens in a different order count separately: with tokens 1 and 2 and a fare of 3, both 1 then 2 and 2 then 1 count. If fare = 0 the turnstile is already open, so return 1.
Example 1
tokens [1,2]
fare 3
returns 3
The sequences are 1+1+1, 1+2 and 2+1.
Example 2
tokens [2,5]
fare 9
returns 3
Nine is two 2s and one 5, and the 5 can be inserted first, second or third.
Constraints
1 <= len(tokens) <= 5, the amounts are distinct1 <= tokens[i] <= 200 <= fare <= 30
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Two-Lane RoadEasy
- Best Stretch SumMedium
- Cheapest DescentMedium
- Cheapest Pool PassesMedium
- Coins From Either EndMedium
- Count DerangementsMedium
- Count the Free PlotsMedium
- Dice Sum WaysMedium