Jump Routes to a Goal

Medium

A grasshopper starts at point 0 on a number line and only jumps forward. Every jump has one of the lengths listed in jumps (all distinct), and each length can be used any number of times. A **route** is a sequence of jump lengths that lands the grasshopper exactly on point total. Routes made of the same jumps in a different order count as **different** routes. Return the number of routes. The answer can be very large; return it exactly.

Example 1

jumps=[1, 2], total=4 → 5

Five routes: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2. The routes 1+1+2 and 2+1+1 are different, because the order of jumps matters.

Example 2

jumps=[3, 5], total=8 → 2

Both 3 + 5 and 5 + 3 work, so there are two routes.

Example 3

jumps=[4, 6], total=7 → 0

Both jumps are even and 7 is odd, so the goal cannot be hit exactly.

Constraints

1 ≤ length of jumps ≤ 200
1 ≤ jumps[i] ≤ 1000
All values in jumps are distinct
1 ≤ total ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium

Input

jumps=[1, 2], total=4

Expected

Run checks the first 3 tests in your browser. Submit checks all 113 tests on the server, hidden ones included.