Related Tags

problem
coin
change
memoization

Coin change problem 2: finding the number of ways to make a sum

This version of the coin change problem deals with finding the total number of ways that an amount of money can be made using specific coins only.

For example, if 10 cents are needed, and you can only use coins of the amounts 2,5, and 8; then 10 cents can be created in exactly three ways: {2, 2, 2, 2, 2}, {5, 5} and {2, 8}.

Using sub-problems

Since this problem is solved using Dynamic Programming (DP), the solutions to the sub-problems must be utilized to reach the original problem’s solution – a two-dimensional array will store the sub-problems’ solutions.

Below is the solution to this version of the coin change problem:

1. If the highest coin does not exceed the required sum, then the number of ways that the sum can be made will be equal to the number of ways that the same sum can be made without the highest coin + the number of ways in which a value of sum - highest coin can be made.
2. Else, if the highest coin exceeds the required sum, then the number of ways this sum can be made is equal to the number of ways it could be made without this coin.

The array

A 2-D array (arr) will be used in this solution. A 1-D array may be used as well, but the following explanation cannot be applied to it:

The value at arr[i][j] represents the number of possible ways that the sum j can be made using the first i coins only.

Implementation

#include <iostream>

using namespace std;

int findPossibleWays(int coins[], int sum, int size){
// Declaring a 2-D array
// for storing solutions to subproblems:
int **arr = new int*[size + 1];
for(int i = 0; i < size + 1; i++)
arr[i] = new int[sum + 1];

// Initializing first column of array to 1
// because a sum of 0 can be made
// in one possible way: {0}
for(int i = 0; i < size + 1; i++)
arr[i][0] = 1;

// Initializing first row of array to 0
// because a sum cannot be made with no coins:
for(int j = 0; j < sum + 1; j++)
arr[0][j] = 0;

// Applying the recursive solution:
for(int i = 1; i < size + 1; i++)
for(int j = 1; j < sum + 1; j++)
if(coins[i - 1] > j)
arr[i][j] = arr[i - 1][j];
else
arr[i][j] = arr[i - 1][j] + arr[i][j - coins[i - 1]];

// Freeing memory from heap:
for(int i = 0; i < size + 1; i++)
delete[] arr[i];
delete[] arr;

}

int main(){
// Declaring array of available coins:
int coins[] = {1, 2};
int size = sizeof(coins) / sizeof(coins[0]);

// The sum to be made:
int sum = 5;

cout << "Number of possible ways in which " << sum
<< " can be made is " << findPossibleWays(coins, sum, size)
<< endl;

return 0;
}


RELATED TAGS

problem
coin
change
memoization