Given a number S and coins of values V = {v_{1}, v_{2},v_{3}, v_{4}}. Find the number of ways change can be made for S using these coins.We have an infinite supply of these coins. Commonly, this problem is known as the coin change problem. For example,

Input:N = 4; S = {1,2,3}Output:4Explanation:There are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}

## Thoughts

As always, let’s start with a 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 the reduced problems too.

If a coin is not included in a solution when the value to change is less than the denomination of the coin. At this time, there is a 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 the 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 the 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 points when we can stop going forward. That’s a perfect condition for a recursive solution.

### 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 the 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 the value required by no coins left, there is no 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 ^{m})` where

`m`is number of coins.

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 ^{2}`. For

`m`coins, it will be

`2`. In all these options we will be checking whether that selection has made the change which is required

^{m}The reason for this exponential complexity is that we are calculating smaller subproblems again and again.

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

To avoid calculating the same subproblem again and again, that we can avoid using simple memorization. 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 answered to the problem.

### Show me the dynamic programming implementation

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.

The complexity of dynamic programming implementation of the coin change problem is `O(Nm)` where `N` is value and `m` is the 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 [email protected]