Coin Change Problem - 1

The motivation for this article is from the Coin Sums problem on Project Euler+. The Coin Change Problem has troubled me a lot so here is an explanation for other troubled souls who come in search for solutions and wisdom.

Problem Statement

“Given the total sum and the types of coins find the number of ways that the sum can be formed using an infinite supply of the coins”

Note the order of coins does not matter. (1,1,2) is the same as (1,2,1) for a sum of 4.

Logic

To count the number of ways to make change for a particular value N we can choose any coin c and then count the number of ways to make change for the value N - c. Now if we consider these coins sequentially we can decide to do either one of these -

1. Include this coin in calculating our answer and then find the number of ways to make a change of N-c value.
2. Exclude this coin in calculating our answer and in any further calculations.

Let the types of coins (denominations) be the same as that in Q31 of Project Euler+. We can represent our coins as a 1D vector. vector<int> coins = {1,2,5,10,20,50,100,200};
Let index denote the current coin that we are having a look at.

So our code is something like this now:

int noOfWays(int N, int index)
{
    /*
    calculate the number of ways to make N value with the given denominations considering the coin at position index
    */
    if(N == 0) return 1; //we have found a way
    if(N < 0) return 0; //it is not possible
    if(index < 0) return 0; //it is not possible
    return noOfWays(N,index-1) + noOfWays(N-coins[index],index);
    //case 1: we exclude the index'th coin from counting
    //case 2: we include the index'th coin in this and further counting
}

All we need to do now is to memorize the solution so that we handle each case only once. The code would look something like this now -

int noOfWays(int N, int index)
{
    map<pair<int,int>,int> mp;
    if(N == 0) return 1;
    if(N < 0) return 0;
    if(index < 0) return 0;
    if(mp.find({N,index}) != mp.end()) return mp[{N,index}]; //if we have seen this pair of value previously then return it
    return mp[{N,index}] = noOfWays(N,index-1) + noOfWays(N-coins[index],index); //otherwise store the value and then return it
}

That’s it! In less than 10 lines we have solved the Coin Change Problem! :D