Array String Dynamic Programming Memoization Tabulation
Intermediate Level

Implement the coinChangeCombinationCount method that counts coin combinations that can make the amount.

The input contains coin denominations coins, their count size, and a target amount.

Your task is to count how many different combinations can form the amount. Each coin denomination may be used multiple times, and combinations with the same coin counts are considered the same even if the order is different.

For example, with coins [1,2,5] and amount 5, the 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 combinations that can form amount x.

Start with dp[0] = 1 because there is one way to make amount zero: choose no coins. Then process each coin one by one. For every amount from that coin value to the target, add the combinations from amount - coin.

Processing coins in the outer loop prevents counting the same combination multiple times in different orders.

Pseudocode:

function coinChangeCombinationCount(coins, size, amount):
    dp = array of amount + 1 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.