Coin Changing Problem

Given an infinite number of different domination coins, calculate the number of ways of representing n rupees

Solution :

• One simple ways try to make N money with M type of coins this ways
  • N money with M-1 types of coins +
  • N – Amount[M] with M types of coins

Recursive Algorithm:

1. If money == 0 then
   1. return 1 (i.e. only way to make money 0 with any kind of coins)
2. If index >= total coins then
   1. return 0
3. Iterate till computedAmount <= money
   1. recursively call to make computedAmount with M-1 coins
   2. remaining amount with with N coins

Latest Source Code:
Github: CoinChangingProblem.java

Output:

Total ways (recursive): 5
Total ways (with memo): 5

Video

Video

Video