Array Math Dynamic Programming Tabulation
Proficient Level

Implement the countWaysToMakeAmount method that counts how many combinations can make the target amount using coins.

The input contains a list of coin denominations coins, its length size, and a target amount. Your task is to count how many different combinations of coins can make exactly that amount.

You may use each coin denomination any number of times. The order of coins does not create a new way. For example, with coins [1,2,5] and amount 5, the valid combinations are 5, 2+2+1, 2+1+1+1, and 1+1+1+1+1, so the answer is 4.

Example 1
Input:
coins (int[]) = [1,2,5]
size (int) = 3
amount (int) = 5
Return:
(int) 4
Example 2
Input:
coins (int[]) = [2]
size (int) = 1
amount (int) = 3
Return:
(int) 0
Example 3
Input:
coins (int[]) = [10]
size (int) = 1
amount (int) = 10
Return:
(int) 1

Use dynamic programming where dp[x] stores the number of ways to make amount x.

Start with dp[0] = 1 because there is one way to make amount zero: choose no coins. For every coin, update all amounts from that coin value up to the target amount.

Processing coins one by one ensures that combinations are counted once and different orders are not counted separately.

Pseudocode:

function countWaysToMakeAmount(coins, size, amount):
    dp = array of amount + 1 values filled with 0
    dp[0] = 1
    for each coin in coins:
        for value from coin to amount:
            dp[value] = dp[value] + dp[value - coin]
    return dp[amount]
Run your code to see the result.