Example: Coin changing combination problem - rFronteddu/general_wiki GitHub Wiki

This problem is known as the Coin Change II problem. The goal is to find the number of possible ways to make up a given total amount using an unlimited supply of coins of different denominations.

Problem Description You are given:

• An array coins of distinct integers representing different denominations.
• An integer total representing the target amount.

You need to find the number of unique combinations of coins that sum up to total.

Key Points

• Each coin can be used an unlimited number of times.
• The order of coins in combinations does not matter (i.e., 1, 2, 1, 2 is the same as 2, 1, 1, 2).

Recommended solution

public int change(int total, int[] coins) {    
    // Initialize dp array with zeros, and dp[0] as 1 (base case)
    int[] dp = new int[total + 1];
    dp[0] = 1; // There is one way to make 0 amount (using no coins)
        
    // Loop through each coin
    for (int coin : coins) {
        // Update dp array for each value from coin to total
        for (int i = coin; i <= total; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[total];
}

Old 2D approach

• X = 1,2,3
• tot = 5

--	0	1	2	3	4	5
1	1	1	1	1	1	1
2	1	1	2	2	3	3
3	1	1	2	3	4	5

// x[1..n]
maxCoinComb(x)
    let d[1..n, 0..tot] be a table
    for i = 1 to n
        d[i,0] = 1 // how many combinations to get 0 total? 1 -> no coins
    for j = 0 to total
        d[0,j] = 1 // this assumes there is a coin of value 1
    for i = 2 to n
        for j = 1 to total
            if(x[i] < j)
                d[i,j] = d[i-1,j]
            else 
                d[i,j] = d[i-1,j] + d[i, j - x[i]] // include the coin + exclude the coin

    return d[n,tot]