Hello everyone, just a small tutorial on Coin Change Problem.

### Problem:

Given a number of dollars, , and a list of dollar values for distinct coins, , find and print the number of different ways you can make change for dollars if each coin is available in an infinite quantity.

https://www.hackerrank.com/challenges/ctci-coin-change

Solution:

Before coding let’s discuss the problem and solution:

Assume you have unlimited change of { 2, 3, 5, 6}, now you have to tell in how many ways you can make a 10$.

There are many possible ways like, {2,2,2,2,2,} , {2,3,5}.

But how to determine the solution of problem?

There is a **recursive solution**, in which try all the combinations and if right one is found, increment the count. But doing it recursively is a complex task and the complexity will be O(power(n,m)) and the code is:

package main import ( "fmt" "sort" ) var ways int func coinchange(startIndex int, totalMoney int , coins []int) { if startIndex < 0 { return } if totalMoney < 0 { return } if totalMoney == 0 { ways++ return } for i := startIndex;i>=0;i-- { coinchange(i,totalMoney-coins[i],coins) } } func main() { var money, numCoins int fmt.Scanf("%d%d",&money, &numCoins ) k := make([]int,numCoins) for i:=0;i<numCoins;i++ { fmt.Scanf("%d",&k[i] ) } // sort to optimize the calulation sort.Ints(k) coinchange(numCoins-1,money,k) fmt.Println(ways) }

and this is my output with recursive solution :

The solution is fine and clears few of the test cases, but it gets timeout for the large dataset. The basic problem is while designing our solution we are solving the problems again and again. Like, {6,4} is 10 and {6,2,2}is 10 and {2,2} is 4 and we are recalulating it again and again.

### To to solve this we will use Dynamic programming.

package main import "fmt" func main() { var money, numCoins int fmt.Scanf("%d%d",&money, &numCoins ) k := make([]int,numCoins) for i:=0;i<numCoins;i++ { fmt.Scanf("%d",&k[i] ) } // make a DP array dp := make([]int,money+1) dp[0] = 1 for i:=0;i<numCoins;i++ { start := k[i] for j:=start;j<=money;j++ { // use the saved solution dp[j] += dp[j-start] } } fmt.Println(dp[money]) }

Our DP Solution clears all the test cases on Hacker rank.

### Explanation:

Now we need a way to save the solution of already solved problems, we will use an array for same.

Map this diagram with code comments and you will figure it out.

Bye everyone, happy coding.