Problem D. Coin Change

The tasks in this section contain test function calls. Please do not change this code; otherwise, the assignment may not be accepted.

The problem is to find the possible number of ways to get N cents with coins of different denominations. Imagine you have an infinite amount of coins valued c[0], c[1], c[2], …, c[m-1] – some values (for example, coins of 1, 2, 5, and 10 cents; these values are stored to input as an array).

You can combine these coins to achieve N cents in sum. Calculate the number of possible variations.

Order does not matter, i. e. for N=10 combinations 1+2+2+5, 2+1+2+5, and 5+2+1+2 are equal.

Example 1: N = 5, coins = [1,2,5] -> 4

There are 4 ways to combine coins: 5=1+1+1+1+1, 5=1+1+1+2, 5=1+2+2, 5=5.

Example 2: N=4, coins=[1,2,3,7] -> 4

Answer is 4: 4=1+1+1+1, 4=2+2, 4=1+3, 4=1+1+2

Example 3: N=100, coins = [1,3,5,7,10] -> 6426