Statement

Given a fixed list of numbers, [1,3,4][1, 3, 4], and a target number, nn, count all the possible ways in which nn can be expressed as the sum of the given numbers. If there is no possible way to represent nn using the provided numbers, return 00.

Note: You may assume that you can use a specific number as many times as you want. Additionally, the order in which we select numbers from the list is significant.

Let's say nn is 4, then using the given numbers, 11, 33, and 44, the target number nn can be expressed in the following four ways:

  • Using 11 four times: 1+1+1+1=41+1+1+1 = 4.

  • Using a 11 and then a 33: 1+3=41 + 3 = 4.

  • Using a 33 and then a 11: 3+1=43+1=4.

  • Using only 44: 4=44=4.

Constraints:

  • 0<=n<=9500 <= n <= 950

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.