FunctionRacerProblemsRace

Token Orders at the Turnstile

EasyDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems