Coin Change Problem

Coin change problem is very similar to unbounded knapsack problem which can be solved easily and efficiently by using Dynamic Programming. General task is to find maximum number of ways to add the coins from the array for given amount. Here supply of each type of coin in an array is limitless.

Here we will see recursice aprroach and dynamic programming approach a approach to solve this problem.

Coin Chnage Problem - Maximum number of Ways

Problem Statement:

Given an amount and an array of coins showing available coins. Determine in how many ways coins can be added for the amount. There is limitless supply of coins of each type.

Example:

    coin[] = [1,2,3]
    amount = 5
    
    Ways coins can be added to get amount = 5:
    1) 1+1+1+1+1 = 5
    2) 1+1+1+2 = 5
    3) 1+1+3 = 5
    4) 1+2+2 = 5
    5) 3+2 = 5
    
    There are 5 ways, therefore output should be 5 for this example.

Recursive Approach

In the recursive approach first we'll have a base condition - if amount is 0 then there is only one way (empty array) so we'll return 1 and if given coin array is empty and amountn is not zero then there is no way so we'll return 0. Else for each coin function will have two calls.

Say coin array is {1,2,3} and amount is 5:

                            {}
                          /     \
                         /       \
                       {2}         {} 
                     /    \        /   \
                    /      \      /     \ 
                   /        \    /       \
               {2,3}        {2}  {3}         {}
             /    \        /  \   / \       /   \
            /      \      /    \ /   \     /     \
       {2,1,3}   {2,3} {2,1} {2}{3,1} {3}  {1}   {}
                    .
                    .
                    .
                    and so on
                    

i.e for every coin we'll have 2 functions calls either the coin is included or excluded. If coin is included then function call will be made at n i.e maxWays(coin, amount-coin[n-1], n) and if it is excluded then function call is made at n-1 i.e. maxWays(coin, amount, n-1)

Time Complexity:

Recursive approach to solve this problme is very easy to implement and understand.
But it's time complexity is exponentitial and in rare cases it may cause stackoverflow error.
Time Complexity: O(2^n)

#include<iostream>
using namespace std;


int maxWays(int coin[], int amount, int n){
    //Base Condition
    if(amount == 0)
        return 1;
    else if(n == 0 && amount != 0)
        return 0;
    //Choices
    else if(coin[n-1] <= amount)
        return (maxWays(coin, amount-coin[n-1], n) + maxWays(coin, amount, n-1));
    else
        return maxWays(coin, amount, n-1);
}

int main(){

    int coin[] = {1,2,3};
    int amount = 5;
    int n = sizeof(coin)/sizeof(coin[0]);

    cout<<"Maximum number of ways are "<<maxWays(coin, amount, n);
    
}

Dynamic programming Aprroach

We will start by building a 2D matrix where rows resembles to coins and columns resembles to the amounts.
let's matrix be t[n+1][amount+1], where n is the size of coin array.

Initialization of t[n+1][amount+1] : If amount is 0 then there is only one way i.e. empty array and if amount is non-zero and size of array is 0 then there is no way for the amount so output will be 0.

    for(int i =0; i < n+1; i++){
        for(int j = 0; j < amount+1; j++){
            if(j==0)
                t[i][j] = 1;
            else if(i==0 && j!=0)
                t[i][j] = 0;
        }
    }

For each coin there are two possibilities:

• If the coin value is larger than amount then it'll be excluded

t[n][amount] = t[n-1][amount]

• Else object will be taken or excluded

if object is included then 
    t[n][amount] = t[n][amount-coin[n-1]]

if object is not included then
    t[n][amount] = t[n-1][amount]

In short structure for computing t[n][amount]

    t[n][amount] = t[n][amount-coin[n-1]] + t[n-1][amount], if coin[n-1] <= amount
    t[n][amount] = t[n-1][amount], otherwise

Logic:

for(int i = 1; i < n+1; i++){
        for(int j = 1; j < amount+1; j++){
            if(coin[i-1] <= j) 
                t[i][j] = t[i][j-coin[i-1]] + t[i-1][j]; 
            else
                t[i][j] = t[i-1][j]; 
        }
    }

Answer:

t[i][j]

Let's see how above logic works with simple examples :
Example
coin = {1,2}
amount = 3
here n is 2 (size of coin array)
first initialize the t[n+1][amount+1] (i.e. t[3][4])
so the t[][] matrix will look something like-

1 0 0 0
1 _ _ _
1 _ _ _

For now we are just focusing on initialisation, other values we'll be filling step by step
Now at i=1 and j=1
Here i indicates n and j indicates amount
so for this instance coin={1} and amount=1

if(coin[i-1]<=j) //True
   t[i][j] = t[i][j-coin[i-1] + t[i-1][j]
   t[1][1] = t[1][0] + t[0][1]
   t[1][1] = 1+0; //from initialised matrix t[][]
   t[1][1] =1

now t[][] matrix will look like

1 0 0 0
1 1 _ _
1 _ _ _

At i=2 and j=1
At this step n(size of coin array)=2 and amount=1
coin={1,2}

check (coin[i-1]<=j) //False as coin[1]=2 which is greater than j(j=1)
t[i][j] = t[i-1][j]
so
t[2][1] = t[1][1]
t[2][1] = 1 //check value of t[1][1] from matrix in the previous step

now t[][] matrix will look like

1 0 0 0
1 1 _ _
1 1 _ _

If you keep following this logic the t[][] matrix will finally look like-

1 0 0 0
1 1 1 1
1 1 2 2

Our answer is t[n][amount] (in example n=2 and amount=3)
So max number of ways = t[2][3] = 2

Time Complexity

• Time Complexity: O(n * amount)
• Space Complexity: O(n * amount)

Implementation

#include<iostream>
using namespace std;

int main(){
    int coin[] = {1,2,3};
    int amount = 5;
    int n = sizeof(coin)/sizeof(coin[0]);
    int t[n+1][amount+1];

    //Initialization
    for(int i =0; i < n+1; i++){
        for(int j = 0; j < amount+1; j++){
            if(j==0)
                t[i][j] = 1;
            else if(i==0 && j!=0)
                t[i][j] = 0;
        }
    }

    //across the rows
    for(int i = 1; i < n+1; i++){
        
        //across the columns
        for(int j = 1; j < amount+1; j++){
        
            // we can include or exclude the coin
            if(coin[i-1] <= j) 
                
                //if value of coin is less than or equal to the amount the we'll 
                //have two choices : Include the coin or exclude the coin
                t[i][j] = t[i][j-coin[i-1]] + t[i-1][j]; 
            else
                // Excluding the coin
                t[i][j] = t[i-1][j]; 
        }
    }

    cout<<"Maximum number of ways are "<<t[n][amount];
}

Value of t[i][j] stands for what?

Here every value of t[i][j] stands for maximum ways to make the amount=j when an array contains i number of coins.
example: let's say for coin array mentioned above if t[1][2] = 1
This means for this instance j=2 i.e. amount=2
number of coins in an array is 1 so from coin[]={1,2,3} only first coin
is coinsidered i.e. for an instance coin array looks like {1}
We can see there is only 1 way to make amount 2 by using coin of 1 (1+1 = 2)

Example

Input: int coin[] = {1,2,3};
       int amount = 5;
Output: Maximum number of ways are 5

t[n][amount] for above example will be

1 0 0 0 0 0
1 1 1 1 1 1
1 1 2 2 3 3
1 1 2 3 4 5