DIY: Coin Change 2

Problem statement

Given an integer amount representing the total amount of money and a list of integers called coins where each coin[i] contains a unique coin with a different denomination.

You have to find the total number of ways that can make up the amount by using the combinations of these coins. If any combination cannot make up the amount return 0.

We may assume that we have an infinite number of coins of each denomination

Constraints

• The number of coins in the coins list will be in the range [1,300].
• The denomination of every coin[i] in the coins list will be in the range of [1,5000].
• The values of all the coins will be unique.
• The amount will be in the range of [0,5000].

Input

The first input will be a list of integers called coins, and the second input will be an integer called amount. The following are example inputs:

// Example 1
coins = [1,2,5]
amount = 5

// Example 2
coins = [4]
amount = 6

// Example 3
coins = [5]
amount = 5

// Example 4
coins = [1,2,5]
amount = 0

Output

The output will be an integer that represents the total number of coins needed to make up the amount. The followings are sample outputs to the above inputs:

// Example 1
4

// Example 2
0

// Example 3
1

// Example 4
0

Coding exercise

Implement the function change(coins, amount) in the skeleton code below.