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.

Here we have 3 set of coins {1, 2, 3} and we need to make a sum of money “8” all the 10 combinations are as showing in the picture.

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) = \sum_{k=1}^K F({1...K-1}, N - coin[K]) // 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 O(K^N).

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 O(K*N).

012345678
1111111111
2112233445
31123457810
solutions memory for dynamic programming approach.

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:
Advertisements