Coin Change Problem - 2

Problem Statement

“Given the total sum and the types of coins find the minimum number of coins that can be used to get to this sum”

Note the order of coins, as in the previous question, does not matter.

Logic

The logic for this question is pretty much the same as that of the previous.
However as we now want to return the minimum number of coins instead of returning the number of coins in each step of the recursion.

So our code is something like this now:

int minCoins(int N,int index)
{
	if(N == 0) return 0; //no of ways to make change of 0 value is 0
	if(N < 0) return INF; //it is impossible to make a negative value so we return an impossible value
	if(index < 0) return INF; //if the values that we can choose become empty we return an impossible value
	return min(minCoins(N,index-1), 1 + minCoins(N-coins[index],index))
  //case 1: we exclude the index'th coin from counting and find the minimum ways without it
  //case 2: we include the index'th coin in this and further counting
}

We can memoize this solution too like we did in the previous case. I’ll leave that part upto you :)

Annnnnd that is it! We have successfully solved this question by just tweaking the base cases of our previous solution!