Coin change problem (Find all number of combinations that formed a sum amount with given denominations)

Given a set of denominations of coins and an amount, our aim is find number of combinations in which we can arrange denominations to form our input amount. Let’s understand this better with following example.

We can solve this problem using below two different approaches.

1. Recursion
2. Dynamic Programming.

Recursion

Let’s divide our problem into smaller pieces to define the recursion formula. Let’s consider we used our coin “1” to make our sum “8” now as we already used coin “1”, now the remaining sum becomes “7”, we have to use the same set of coins again to make money “7”.

// Formula for recursion.
F({1, 2, 3}, 8) = 1 + F({1, 2, 3}, 7)
                = 1 + 1 + F({1, 2, 3}, 6)
                  ...
                = 1 + 1 + 1 + 1 + 1 + 1 + 1 + F({1, 2, 3}, 0) (which is 1 again)
// Once the sum reaches to zero that makes one of the different combinations

// So, our formula becomes
F({1..k}, N) = 1 // If N = 0
F({1..k}, N) = // If N is greater than 0.

Let’s see the code for this recursion solution.

int findCombinations(int coins[], int n, int amount, int currentCoin)
{
    if (amount == 0)
    {
        return 1;
    }
    else if (amount < 0)
    {
        return 0;
    }
    int combs = 0;
    for (int i = currentCoin; i < n; i++)
    {
        combs += findCombinations(coins, n, amount - coins[i], i);
    }
    return combs;
}

Complexity of this solution is .

Dynamic Programming

Recursion solution is very slow as it is an exponential complexity solution. We need to think a better approach to solving this problem, here it comes with dynamic programming which we can solve with .

	0	1	2	3	4	5	6	7	8
1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	3	3	4	4	5
3	1	1	2	3	4	5	7	8	10

Let’s understand the formula for this dynamic programming.

dp[i][j] = 1           // if j=0
         = 1 or 0      // 1 if sum % coins[i] is 0, otherwise '0'
         = dp[i-1][j]  // if j < coins[i]
         = dp[i-1][j] + dp[i][j-coins[i]]  // if j >= coins[i]

We are going to apply this formula and write the code to solve this problem.

int combinationUsingDP(int coins[], int n, int amount)
{
    int dp[n][amount + 1];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= amount; j++)
        {
            if (j == 0)
            {
                dp[i][j] = 1;
                continue;
            }
            if (i == 0)
            {
                dp[i][j] = (j % coins[i] == 0) ? 1 : 0;
                continue;
            }
            if (j >= coins[i])
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n - 1][amount];
}

These are the two different approaches to solve the coin change problem. The full code with the main function is as showing below.

// Output
10
10

This is all about coin change problem, if you know any better approach to solve this problem please let our readers know by commenting here below. Happy Learning!.

See more:

0/1 Knapsack problem example with recursion and dynamic programming solutions

House thief problem (using recursion and dynamic programming)