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](https://www.educative.io/answers/what-is-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*.

#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]];
    
    int answer = arr[size][sum];
    
    // Freeing memory from heap:
    for(int i = 0; i < size + 1; i++)
        delete[] arr[i];
    delete[] arr;
    
    return answer;
}

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;
}


class CoinChanger2 { 

    static int findWays(int[] coins, int sum) {
      // Declaring a 2-D array
      // for storing solutions to subproblems:
    	int size = coins.length;
    	int[][] arr = new int[size + 1][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;
    	
      // Applying the recursive solution:
    	for(int i = 1; i < size + 1; i++)
    		for(int j = 0; j < sum + 1; j++)
    			if(coins[i - 1] > j)  // Cannot pick the highest coin:
    				arr[i][j] = arr[i - 1][j];
    			else  // Pick the highest coin:
    				arr[i][j] = arr[i][j - coins[i - 1]] + arr[i - 1][j];
    	
    	return arr[size][sum];
    }
  
    public static void main(String args[]) 
    { 
        int coins[] = {1, 2};  // Declaring array of coins
        int sum = 5;  // The sum to be made

        System.out.println("The possible ways in which " + sum
        		+ " can be made is " + findWays(coins, sum));
    } 
}


Java

def find_possible_ways(coins, sum):
    size = len(coins)

    # Declaring a 2-D array
    # for storing solutions to subproblems:
    arr = [[0] * (sum + 1) for x in range(size + 1)]

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

    # Applying the recursive solution:
    for i in range(1, size + 1):
        for j in range(1, sum + 1):
            if coins[i - 1] > j:  # Cannot pick the highest coin:
                arr[i][j] = arr[i - 1][j]
            else:  # Pick the highest coin:
                arr[i][j] = arr[i - 1][j] + arr[i][j - coins[i - 1]]

    return arr[size][sum]


coins = [1, 2]  # Array of available coins
sum = 5  # The sum to be made

print("The possible ways %s can be made is %s" % (sum, find_possible_ways(coins, sum)))


Python

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

Dynamic Programming finds the number of ways to make a sum using specific coins by utilizing sub-problems' solutions in a 2-D array.

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

Using sub-problems

The array

Implementation