**Objective: **Given a set of coins and amount, Write an algorithm to find out how many ways we can make the change of the amount using the coins given.

This is another problem in which i will show you the advantage of Dynamic programming over recursion.

**Example**:

Amount = 5 coins [] = {1,2,3} Ways to make change = 5 {1,1,1,1,1} {1,1,1,2}, {1,2,2}, {1,1,3} {2,3}

**Approach:**

**Recursive Solution: **

- We can solve it using recursion.
- For every coin we have an option to include it in solution or exclude it.
- See the Code

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class CoinChangeRecursion { | |

public static int total(int n, int[] v, int i) { | |

if (n < 0) { | |

return 0; | |

} | |

if (n == 0) { | |

return 1; | |

} | |

// means coins over and n>0 so no solution | |

if (i == v.length && n > 0) { | |

return 0; | |

} | |

return total(n – v[i], v, i) + total(n, v, i + 1); | |

} | |

public static void main(String[] args) { | |

int amount = 5; | |

int[] v = { 1, 2, 3 }; | |

System.out.println("By Recursion: " + total(amount, v, 0)); | |

} | |

} |

**Time Complexity** : **2 ^{n}**

I have been asked that by many readers that how the complexity is 2^n . So including a simple explanation-

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 n coins , it will be 2^n. In all these options we will be checking whether that selection has made the change which is required.

But if we notice that we are solving many sub-problems repeatedly.

We can do better by applying Dynamic programming.

**Dynamic Programming: Bottom-up –**

Earlier we have seen “Minimum Coin Change Problem“. This problem is slightly different than that but approach will be bit similar.

Create a solution matrix. (solution[coins+1][amount+1]).

**Base Cases: **

- if amount=0 then just return empty set to make the change, so 1 way to make the change.
- if no coins given, 0 ways to change the amount.

**Rest of the cases:**

- For every coin we have an option to include it in solution or exclude it.
- check if the coin value is less than or equal to the amount needed, if yes then we will find ways by including that coin and excluding that coin.

**Include the coin**: reduce the amount by coin value and use the sub problem solution (amount-v[i]).**Exclude the coin**: solution for the same amount without considering that coin.

- If coin value is greater than the amount then we can’t consider that coin, so solution will be without considering that coin.

**Equation:**

solution[coins+1][amount+1]

= | 0 | if i=0 | |

solution[i][j] | = | 1 | if j=0 |

= | solution[i – 1][j] + solution[i][j – v[i – 1]] | if(coin[i]<=j) | |

= | solution[i – 1][j]; | if(coin[i]>j) |

Example:

Amount = 5 coins [] = {1,2,3}

**Code**:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class WaysToCoinChange { | |

public static int dynamic(int[] v, int amount) { | |

int[][] solution = new int[v.length + 1][amount + 1]; | |

// if amount=0 then just return empty set to make the change | |

for (int i = 0; i <= v.length; i++) { | |

solution[i][0] = 1; | |

} | |

// if no coins given, 0 ways to change the amount | |

for (int i = 1; i <= amount; i++) { | |

solution[0][i] = 0; | |

} | |

// now fill rest of the matrix. | |

for (int i = 1; i <= v.length; i++) { | |

for (int j = 1; j <= amount; j++) { | |

// check if the coin value is less than the amount needed | |

if (v[i – 1] <= j) { | |

// reduce the amount by coin value and | |

// use the subproblem solution (amount-v[i]) and | |

// add the solution from the top to it | |

solution[i][j] = solution[i – 1][j] | |

+ solution[i][j – v[i – 1]]; | |

} else { | |

// just copy the value from the top | |

solution[i][j] = solution[i – 1][j]; | |

} | |

} | |

} | |

return solution[v.length][amount]; | |

} | |

public static void main(String[] args) { | |

int amount = 5; | |

int[] v = { 1, 2, 3 }; | |

System.out.println("By Dynamic Programming " + dynamic(v, amount)); | |

} | |

} |

Output:By Dynamic Programming 5