# Coin change problem

Given a number S and coins of values V = {V1,V2,V3, V4}. Find number of ways change can be made for S using these coins.We have infinite supply of these coins. Commonly, this problem is known as coin change problem.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4.

## Coin change problem : Line of thought

As always, let’s start with brute force solution. We have two choices for a coin : Either we can include the coin in solution, or we can not include it in solution. If coin `m`

is included in solution, problem reduces to find change for value `N-V(m)`

using `K`

coins. Notice that we can again use all the coins for reduced problem too.

If coin is not included in solution when value to changed is less than the denomination of coin. At this time, there is reduction in value to be changed, but we lose one coin, hence problem stands : Change value V with N-1 coins.

If we look at it, it is simple recursive formulation.

C(N,m) = C(N,m-1) + C(N- V(m), m)

When do we stop then? When do we know that there is no more solution going forward. If change is required for value zero, there is only one solution possible, which is to include no coin.

C(N,m) = 1 if N == 0

Also, what is solution if we do not have any coins with us at all and there is value to be changed. There is no solution then.

C(N,m) =0 if N > 0 and m < 0

Also, if value required is less than zero, then there is again no solution, given that all coins have positive values.

C(N,m) = 0 if N < 0

We see that problem reduces to smaller problems and then there are point when we can stop going forward. That’s a perfect condition for recursive solution.

### Coin change problem : recursive implementation

package com.company; /** * Created by sangar on 5.5.18. */ public class CoinChange { public static int coinChange(int value, int[] coins, int consideredCoin){ /* If value to be changed is negative, since coins are positives, there is no way to change them */ if(value < 0) return 0; /*When there may or may not be coins, and no value is required, there is one solution which is not to include any coin */ if(value == 0) return 1; /* When there is value required by no coins left, there is not solution */ if(value > 0 && consideredCoin == coins.length) return 0; // When coin is included return coinChange(value-coins[consideredCoin],coins, consideredCoin) //When coin is not included + coinChange(value,coins, consideredCoin + 1); } public static void main(String[] args){ int value = 4; int[] coins = {1,2,3}; int count = coinChange(value, coins, 0); System.out.println(count); } }

Complexity of recursive implementation of coin change solution is exponential `O(2`

where m is number of coins.^{m})

For every coin we have 2 options, either we include it or exclude it so if we think in terms of binary, its 0(exclude) or 1(include). so for example if we have 2 coins, options will be [ 00, 01, 10, 11 ]. so its `2`

. For m coins , it will be ^{2}`2`

. In all these options we will be checking whether that selection has made the change which is required^{m}

Reason for this exponential complexity is that we are calculating smaller subproblems again and again.

In discussion so far, we see two properties of the solution : First, there is optimal substructure, that is optimal solution to subproblems provides optimal solution to bigger problems. This is known as optimal substructure property. Second, subproblems are overlapping. These two condition as necessary for applying dynamic programming approach.

To avoid calculating same subproblem again and again, that we can avoid using simple memoization. Let’s create a two dimensional table Coins. `Coins(i, j)`

represents the number of ways in which change for i can be made using j coins.

Now if j^{th} coin is included, then numbers of ways will be `Coins(i- v[j], j-1)`

If j^{th} coin is not included, number of ways will be `Coins (i, j-1)`

. Adding both of them will give us

Coins(i,j) = Coins(i-v[j]) + Coins(i, j-1).

For all i = 0 Cost(i,j) = 1, for all j = 0 Cost(i,j) will 1 for all i > 0.

We can start bottom up and fill the table as per the formula above. Once we have filled the entire table, Coins(N,m) will be answer to the problem.

package com.company; /** * Created by sangar on 5.5.18. */ public class CoinChange { public static int coinChangeDP(int value, int[] coins){ int[][] numWays = new int[value+1][coins.length+1]; for(int i = 0; i <= coins.length; i++ ){ numWays[0][i] = 1; } for(int i = 1; i <= value; i++ ){ numWays[i][0] = 0; } for(int i = 1; i <= value; i++){ for(int j = 1; j <= coins.length; j++){ numWays[i][j] = (i -coins[j-1] >= 0 ? numWays[i-coins[j-1]][j] : 0 ) + numWays[i][j-1]; } } return numWays[value][coins.length]; } public static void main(String[] args){ int value = 4; int[] coins = {1,2,3}; int count = coinChangeDP(value, coins); System.out.println(count); } }

Example : for Value = 4 and coins {1,2,3}, below is the bottom up filling of table.

Complexity of dynamic programming implementation of coin change problem is O(Nm) where N is value and m is number of coins. Additional O(Nm) space is also required for memoization.

Please share if there is something missing or wrong. If you want to share your knowledge with thousands of learners across the world, please reach out to us on communications@algorithmsandme.com