Number of ways to make coin change | Letuscode

Number of ways to make coin change | Letuscode

Given some amount N, and a set of denominations, how do you find the number of ways to make change for N? Let us assume that there is infinite supply of coins for each denomination. For example, if we have to make change for 4, and the given denominations are {1, 2, 3}, the possibilities are {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}. So there are 4 possibilities in total. Let us try to solve this problem using recursion. Let N be the amount for which we have to make change, and D is the set of denominations. Assume we have a method Count N of current denomination, we can have pseudo code like this Count(N, index) Base case#1: If N < 0 or index < 0 return 0. There is no way to make change for negative numbers or if there are no denominations Base case#2: If N == 0, return 1. There is only one possibility to make change for 0 amount, selecting none. Otherwise return Count(N, index-1) + Count( N-D[index], index ). Either ignore the current denomination (First term),

Read full article from Number of ways to make coin change | Letuscode