# Coins Change Problem

The coins change programming problem is described as below.
Given.
a) Coin to be changed. Say a coin of value \$ 4 is to be changed.
b) Set of available coins. Assumption is that, we have a set of infinite coins of values [ \$ 2, \$ 4 ]
Goal is to find the number of ways of exchanging a coin of bigger value with coins of smaller values.

Example: If a coin of value \$ 4 is to be changed with coins of values [ \$ 2, \$ 4 ], we have 2 ways
a) \$ 4 = \$ 2 + \$ 2
b) \$ 4 = \$ 4
Thus we have 2 ways.

Recurrence relation for coins change problem

Base cases:

• If a coin of value 0 is to be changed, there is always 1 way of getting it changed using any available denominations. Thus,
Â Â Â Â Count_MakeChange (num_coins, coin_value, denominations) = 1; when the coin_value equals 0

• If zero are coins available to make a change, there is no way of getting a change for a coin of value greater than 0. Thus,
Â Â Â Â Count_MakeChange (num_coins, coin_value, denominations) = 0; when num_coins equals 0 and coin_value > 0.

• Try getting the change for the coin of bigger value using a chosen coin from the available set

Â Â Â Â  Note:
Â Â Â Â  a) When the chosen coin is not included in the available set of coins, the num_coins is reduced by 1.
Â Â Â Â  b) When the chosen coin is to be included for coin exchange, the bigger coin value is reduced by the denomination of the chosen coin.

Â Â Â Â Thus we have the below recurrence equation,
Â Â Â Â Count_MakeChange (num_coins, coin_value, denominations) =
Â Â Â Â Count_MakeChange (num_coins - 1, coin_value, denominations) +
Â Â Â Â Count_MakeChange (num_coins, coin_value - denominations [ num_coins - 1 ], denominations);

Â Â Â Â Note: If the current coin is chosen for making a change, then the value of the bigger coin is reduced to coin_value - denominations [ num_coins - 1 ]

Dynamic programming approach for coins change problem

Base case values for coin change problem

Note: A coin of value \$ 0 is included in the set of available coins for making change. This is useful for generating the base cases.

Make change for value Using denomination Ways Hint
\$ 0 \$ 0 1 way () Coin \$ 0 can be obtained using coin \$ 0 by choosing coin \$ 0.
\$ 0 \$ 0, \$ 2 1 way (\$ 0) Coin \$ 0 can be obtained using coins \$ 0, \$ 2 by choosing coin \$ 0.
\$ 0 \$ 0, \$ 2, \$ 4 1 way (\$ 0) Coin \$ 0 can be obtained using coins \$ 0, \$ 2, \$ 4 by choosing coin \$ 0.
\$ 1 \$ 0 0 ways () Coin \$ 1 cannot be obtained using coin \$ 0.
\$ 2 \$ 0 0 ways () Coin \$ 2 cannot be obtained using coin \$ 0.
\$ 3 \$ 0 0 ways () Coin \$ 3 cannot be obtained using coin \$ 0.
\$ 4 \$ 0 0 ways () Coin \$ 4 cannot be obtained using coin \$ 0.

Example:
Consider making change for \$ 4 coin. Coins available in the set contains coins of value [ \$ 2, \$ 4 ].
i.e Filling value in table [ 2 ] [ 4 ]

We get the following cases:
Case a) \$ 4 coin is chosen from the set of available coins for making change.
Case b) \$ 4 coin is not chosen i.e only coins of value \$ 0 and \$ 2 are available for making change.

From the recurrence equation
Count_MakeChange [ num_coins ] [ bigger_coin_value ] =
Count_MakeChange [ num_coins ] [ bigger_coin_value - value [ coin_selected_from_set ] ] +
Count_MakeChange [ num_coins - 1 ] [ bigger_coin_value ]

Thus we get,
Count_MakeChange [ 2 ] [ 4 ] = Count_MakeChange [ 2 ] [ 4 - 4 ] + Count_MakeChange [ 1 ] [ 4 ]
Count_MakeChange [ 2 ] [ 4 ] = Count_MakeChange [ 2 ] [ 0 ] + Count_MakeChange [ 1 ] [ 4 ]
Count_MakeChange [ 2 ] [ 4 ] = 1 + 1 = 2 ways

Time complexity : O ( n * m ), where n is the bigger coin to be exchanged and m is the number of smaller coins to be used for exchanging.

Implementation of coins change problem

``````from typing import List # For annotations

def DPGetChange (coinset : List[int], biggercoin : int) -> int :

num_coins = len (coinset)
dptable = [0] * (num_coins+1)
for r in range (num_coins+1) :
dptable[r] = [0] * (biggercoin+1)

# Coins of values(v) greater than 0 cannot be obtained with coins of value 0
for v in range (1, biggercoin+1) :
dptable[0][v] = 0

# Coin of value 0 can be obtained with any given coins(c) in 1 way
for c in range (num_coins+1) :
dptable[c][0] = 1

for c in range (1, num_coins+1) :
for v in range (1, biggercoin+1) :
if (v >= coinset[c-1]) :
# Exclude last coin in the coinset + Include last coin in the coinset
dptable[c][v] = dptable[c-1][v] + dptable[c][v-coinset[c-1]]
else :
dptable[c][v] = dptable[c-1][v] # Exclude last coin in the coinset

return dptable[num_coins][biggercoin]

def GetChange (coinset : List[int], numcoins : int, biggercoin : int) -> int :

# Coin of value 0 can be obtained with any given values in 1 way
if biggercoin == 0:
return 1

# With no available coins for change, we cannot obtain any value
if numcoins == 0:
return 0

if biggercoin >= coinset[numcoins-1]:
# Get change excluding the last coin in the coin set + Get change including the last coin in the coin set
return GetChange(coinset, numcoins-1, biggercoin) + GetChange (coinset, numcoins, biggercoin-coinset[numcoins-1])
else:
return GetChange(coinset, numcoins-1, biggercoin) # Get change excluding the last coin as it has a bigger value

list_biggercoin = [4, 6, 10, 10]
coin_set = [ [ 1, 2, 3 ], [ 2, 3, 4 ], [ 2, 5, 8, 9, 10 ], [ 8, 9, 10 ] ]
# Bigger coin 4, coinset [ 1, 2, 3 ] # Four ways : (1,1,1,1) (1,1,2) (2,2) (1,3)
# Bigger coin 6, coinset [ 2, 3, 4 ] # Three ways : (2,2,2) (2,4) (3,3)
# Bigger coin 10, coinset [ 2, 5, 8, 9, 10 ] # Four ways : (2,2,2,2,2) (2,8) (5,5) (10)
# Bigger coin 10, coinset [ 8, 9, 10 ] # 1 way : (10)

for i in range(len(list_biggercoin)) :
print("\nCoin set : " + str(coin_set[i]) + " Bigger coin : " + str(list_biggercoin[i]), end = ' ')
print("# [DP] Ways : " + str (DPGetChange(coin_set[i], list_biggercoin[i])), end = ' ')
print("\nCoin set : " + str(coin_set[i]) + " Bigger coin : " + str(list_biggercoin[i]), end = ' ')
print("# [Recursion] Ways : " + str(GetChange(coin_set[i], len(coin_set[i]), list_biggercoin[i])), end = ' ')
``````

Output

``````Coin set : [1, 2, 3] Bigger coin : 4 # [DP] Ways : 4
Coin set : [1, 2, 3] Bigger coin : 4 # [Recursion] Ways : 4
Coin set : [2, 3, 4] Bigger coin : 6 # [DP] Ways : 3
Coin set : [2, 3, 4] Bigger coin : 6 # [Recursion] Ways : 3
Coin set : [2, 5, 8, 9, 10] Bigger coin : 10 # [DP] Ways : 4
Coin set : [2, 5, 8, 9, 10] Bigger coin : 10 # [Recursion] Ways : 4
Coin set : [8, 9, 10] Bigger coin : 10 # [DP] Ways : 1
Coin set : [8, 9, 10] Bigger coin : 10 # [Recursion] Ways : 1
``````
``````#include<iostream>
#include<vector>

using namespace std;

// DP solution for making coin change
int DPGetChange (vector<int>& coinset, int biggercoin) {

int num_coins = coinset.size();
int dptable[num_coins+1][biggercoin+1];

// Coins of values greater than 0 cannot be obtained with coins of value 0
for (int c=1; c<=biggercoin; c++) {
dptable[0][c] = 0;
}

// Coin of value 0 can be obtained with any given coins in 1 way
for (int r=0; r<=num_coins; r++) {
dptable[r][0] = 1;
}

for (int r=1; r<=num_coins; r++) {
for (int c=1; c<=biggercoin; c++) {
if (c >= coinset[r-1]) {
// Exclude last coin in the coinset + Include last coin in the coinset
dptable[r][c] = dptable[r-1][c] + dptable[r][c-coinset[r-1]];
} else {
dptable[r][c] = dptable[r-1][c]; // Exclude last
}
}
}

return dptable[num_coins][biggercoin];
}

// Recursive solution for making coin change
int GetChange (vector<int>& coinset, int numcoins, int biggercoin) {

// Coin of value 0 can be obtained with any given values in 1 way
if (biggercoin == 0)
return 1;

// With no available coins for change, we cannot obtain any value
if (numcoins == 0)
return 0;

if (biggercoin >= coinset[numcoins-1])
return GetChange (coinset, numcoins-1, biggercoin) + // Get change excluding the last coin in the coin set
GetChange (coinset, numcoins, biggercoin-coinset[numcoins-1]); // Get change including the last coin in the coin set
else
return GetChange (coinset, numcoins-1, biggercoin); // Get change excluding the last coin
}

int main(){

int coin1 = 4;
vector<int> coinset_1 = { 1, 2, 3 }; /* Four ways : (1,1,1,1) (1,1,2) (2,2) (1,3) */

int coin2 = 6;
vector<int> coinset_2 = { 2, 3, 4 }; /* Three ways : (2,2,2) (2,4) (3,3) */

int coin3 = 10;
vector<int> coinset_3 = { 2, 5, 8, 9, 10 }; /* Four ways : (2,2,2,2,2) (2,8) (5,5) (10) */

cout << "Number of ways of making coin change using dynamic programming" << endl;
cout << DPGetChange (coinset_1, coin1) << endl;
cout << DPGetChange (coinset_2, coin2) << endl;
cout << DPGetChange (coinset_3, coin3) << endl;

cout << "Number of ways of making coin change using recursion" << endl;
cout << GetChange (coinset_1, coinset_1.size(), coin1) << endl;
cout << GetChange (coinset_2, coinset_2.size(), coin2) << endl;
cout << GetChange (coinset_3, coinset_3.size(), coin3) << endl;

return 0;
}
``````

Output

``````Number of ways of making coin change using dynamic programming
4
3
4
Number of ways of making coin change using recursion
4
3
4
``````
``````class CoinsChange {

// DP solution for making coin change
int DPGetChange (int[] coinset, int biggercoin) {

int num_coins = coinset.length;
int[][] dptable = new int[num_coins+1][biggercoin+1];

// Coins of values greater than 0 cannot be obtained with coins of value 0
for (int c=1; c<=biggercoin; c++) {
dptable[0][c] = 0;
}

// Coin of value 0 can be obtained with any given coins in 1 way
for (int r=0; r<=num_coins; r++) {
dptable[r][0] = 1;
}

for (int r=1; r<=num_coins; r++) {
for (int c=1; c<=biggercoin; c++) {
if (c >= coinset[r-1]) {
// Exclude last coin in the coinset + Include last coin in the coinset
dptable[r][c] = dptable[r-1][c] + dptable[r][c-coinset[r-1]];
} else {
dptable[r][c] = dptable[r-1][c]; // Exclude last
}
}
}

return dptable[num_coins][biggercoin];
}

// Recursive solution for making coin change
int GetChange (int[] coinset, int numcoins, int biggercoin) {

// Coin of value 0 can be obtained with any given values in 1 way
if (biggercoin == 0)
return 1;

// With no available coins for change, we cannot obtain any value
if (numcoins == 0)
return 0;

if (biggercoin >= coinset[numcoins-1])
return GetChange (coinset, numcoins-1, biggercoin) + // Get change excluding the last coin in the coin set
GetChange (coinset, numcoins, biggercoin-coinset[numcoins-1]); // Get change including the last coin in the coin set
else
return GetChange (coinset, numcoins-1, biggercoin); // Get change excluding the last coin
}

void Display (int coin, int[] coin_set) {
System.out.println("Coin to change : " + coin);
System.out.print("Coin set : ");
for (int i=0; i<coin_set.length; i++) {
System.out.print(coin_set[i] + " ");
} System.out.println();
}

public static void main(String[] args) {

int coin1 = 4;
int[] coinset_1 = { 1, 2, 3 }; /* Four ways : (1,1,1,1) (1,1,2) (2,2) (1,3) */

int coin2 = 6;
int[] coinset_2 = { 2, 3, 4 }; /* Three ways : (2,2,2) (2,4) (3,3) */

int coin3 = 10;
int[] coinset_3 = { 2, 5, 8, 9, 10 }; /* Four ways : (2,2,2,2,2) (2,8) (5,5) (10) */

CoinsChange c = new CoinsChange();

System.out.println("Number of ways of making coin change using dynamic programming");
c.Display(coin1, coinset_1);
System.out.println("Ways : [" + c.DPGetChange(coinset_1, coin1) + "]");
c.Display(coin2, coinset_2);
System.out.println("Ways : [" + c.DPGetChange(coinset_2, coin2) + "]");
c.Display(coin3, coinset_3);
System.out.println("Ways : [" + c.DPGetChange(coinset_3, coin3) + "]");

System.out.println("\nNumber of ways of making coin change using recursion");
c.Display(coin1, coinset_1);
System.out.println("Ways : [" + c.GetChange(coinset_1, coinset_1.length, coin1) + "]");
c.Display(coin2, coinset_2);
System.out.println("Ways : [" + c.GetChange(coinset_2, coinset_2.length, coin2) + "]");
c.Display(coin3, coinset_3);
System.out.println("Ways : [" + c.GetChange(coinset_3, coinset_3.length, coin3) + "]");
}
}
``````

Output

``````Number of ways of making coin change using dynamic programming
Coin to change : 4
Coin set : 1 2 3
Ways : [4]
Coin to change : 6
Coin set : 2 3 4
Ways : [3]
Coin to change : 10
Coin set : 2 5 8 9 10
Ways : [4]

Number of ways of making coin change using recursion
Coin to change : 4
Coin set : 1 2 3
Ways : [4]
Coin to change : 6
Coin set : 2 3 4
Ways : [3]
Coin to change : 10
Coin set : 2 5 8 9 10
Ways : [4]
``````