About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Number Of Ways To Make Change Problem

Given a variety of coin denominations existing in a currency system, find the total number of ways a given amount of money can be expressed using coins in that currency system. Assume infinite supply of coins of every denomination.

Example

Input: coins = [1, 2, 3], amount = 3

Output: 3

The three ways are -

  • Using the coin having denomination 1 thrice
  • Using the coin having denomination 3 once
  • Using the coin having denomination 2 once and using the coin having denomination 1 once

 Notes

Two ways are considered different if they use a different number of coins of any particular denomination.

As the answer can be quite large, return it modulo 1000000007.

Constraints:

  • 1 <= total number of denominations <= 100
  • 1 <= denomination of a coin <= 10000
  • 1 <= amount to be expressed <= 10000

Solution

We have provided four solutions.

First, we shall explain a brute force solution using recursion. Then we will be using both iterative and recursive dynamic programming to optimize the brute force solution. Finally we will introduce a nice trick to optimize the memory complexity of our solution with iterative dynamic programming.

The most effective way to approach a dynamic programming problem is -

  • Solve the problem for trivial cases, also known as the base cases.
  • Figure out how the problem can be broken into smaller sub-problems. You also need to figure out which set of variables is necessary and sufficient to pinpoint the current sub-problem that we are trying to solve. This set of variables is known as the states of the problem.
  • Figure out the relationship between the solution to the smaller subproblems and the solution of the whole problem. This relationship, known as the recurrence relation, can be expressed as a recursive function whose parameters are the states of the problem.

How to identify that the problem can likely be solved by the dynamic programming paradigm -

  • Gain experience. If you solve various problems from different domains of algorithms, then you will start to observe a pattern in the dynamic programming problems.
  • Try to break the problem into smaller subproblems and find the relationship between the solution to the smaller sub-problem and the solution to the whole problem. If you can, then most likely the problem can be solved with the dynamic programming paradigm.
  • Try to convert the given problem to one of your known dynamic programming problems. 

 In the following solutions, we would be assuming that there are n different denominations.

 1) recursive_solution

Let the recursive function make_change(idx, target) return the number of ways to make target by using the coins from indices 0 to idx, inclusive. By definition, make_change(n - 1, amount) is what we need to return.

The base cases for this recursive function are:

  • When we are at idx = -1, we need to check if we have target == 0 or not.
  • We can return 0 whenever we have a negative target.

Now let us focus on how to compute make_change(idx, target). We can make the amount target in two ways.

  • by using the coin at index idx: If we use the coin at index idx, our next goal would be to make (target - coins[idx]) by using the coins from indices 0 to idx. Here coins[idx] is the denomination of the coin at index idx. There are make_change(idx, target - coins[idx]) ways in total by definition. Notice that in the following call, even though we updated the parameter target, we did not change the parameter idx because we were allowed to use a coin as many times as we wanted.
  • by not using the coin at index idx: By definition, there are make_change(idx - 1, target) ways in total to do so.

If we combine the two cases, we get the following recurrence relation:

make_change(idx, target) = ( make_change(idx-1, target) + make_change(idx, target - coins[idx]) ) % 1000000007. The mod operation has been used as we need to output the result modulo 1000000007.

Time Complexity:

Exponential.

There are 2n - 1 different subsets of the given coins which we can choose to use to make amount. In each such selection, we can choose to use any type of coin, any number of times. So our solution will try out at least 2n - 1 different solutions in the worst case. Hence the complexity is exponential.

Auxiliary Space Used:

O(n + amount).

Here the auxiliary space is mostly used to maintain the call stack of the recursive calls. It is dominated by the highest possible depth of the call stack. As the smallest denomination for a coin can be equal to 1, so we can not use a coin more than amount times. Also, as we can skip at most n - 1 coins in total to make amount. So in the worst case, we may have a call stack of depth of O(n + amount).

Space Complexity:

Space used for input: O(n).

Auxiliary space used: O(n + amount).

Space used for output: O(1).

So total space complexity: O(n + amount).


// -------- START --------

#define MOD         1000000007
#define MAXN        100
#define MAXVAL      10000

int make_change(int idx, int target, vector &coins){

    if(target < 0){
        return 0; // Invalid state as "target" can not be negative
    }

    if(idx < 0){ // It means that we do not have any other coin left to consider
        if(target == 0){
            return 1;   // The coins we used have summed up to "amount"
        }
        else{
            return 0;   // The coins we used have not summed up to "amount"
        }
    }

    // We have two options for the coin sitting in index "idx"

    // 1. We can use it once now
    // Notice that in the following call we did not change "idx" because we might
    // use this coin again to make "target"
    int ret = make_change(idx, target - coins[idx], coins);

    // 2. We ignore the coin at index idx and move to coin at index idx-1
    ret = (ret + make_change(idx - 1, target, coins)) % MOD;

    return ret;
}

int number_of_ways(vector coins, int amount) {
    return make_change((int) coins.size() - 1, amount, coins);
}

// -------- END --------

 2) recursion_with_memoization

Notice that in the above recursive solution, we may call the make_change(idx, target) function multiple times with the same parameters.

 For instance, consider the given example: There are 3 coin denominations: 1, 2 and 3 and  we have to make the amount 3.

coins[ ] = {1, 2, 3}

amount = 3.

Considering that we started from idx = n - 1 and amount = 3 state, there are two ways to reach idx = 0 and target = 1 state,

  • By using the coin at idx = 1 once.
  • By using the coin at idx = 0 twice.

As the output of make_change(idx, target) is constant, we do not need to compute this output more than once. We can store the result after computing the answer for make_change(idx, target) once. This optimization technique is known as memoization. The data structure that we should use for storing the data depends on the domain of the variables idx and target. There can be n different values of idx and target can range from 0 to amount. Both of the domains of the variables form a consecutive range. So it would be better to use a two dimensional static array than a hash table.

Time Complexity:

O(n * amount).

There are (n * amount) different possible states which we may need to compute in the worst case. So the time complexity is equal to O(n * amount).

Auxiliary Space Used:

O(n*amount) space has been used for memoization.

Space Complexity:

Space used for input: O(n).

Auxiliary space used: O(n * amount).

Space used for output: O(1).

So total space complexity: O(n * amount). 


// -------- START --------

#define MOD         1000000007
#define MAXN        100
#define MAXVAL      10000

int dp[MAXN+3][MAXVAL+3];

int make_change(int idx, int target, vector &coins){

    if(target < 0){
        return 0; // Invalid state as "target" can not be negative
    }

    if(idx < 0){ // It means that we do not have any other coin left to consider
        if(target == 0){
            return 1;   // The coins we used have summed up to "amount"
        }
        else{
            return 0;   // The coins we used have not summed up to "amount"
        }
    }

    // So that we do not calculate the solution to the same state more than once.
    if(dp[idx][target] != -1) return dp[idx][target];

    // We have two options for the coin sitting in index "idx"

    // 1. We can use it once now
    // Notice that in the following call we did not change "idx" because we might
    // use this coin again to make "target"
    int ret = make_change(idx, target - coins[idx], coins);

    // 2. We ignore the coin at index idx and move to coin at index idx-1
    ret = (ret + make_change(idx - 1, target, coins)) % MOD;

    return dp[idx][target] = ret;
}


int number_of_ways(vector coins, int amount) {
    memset(dp, -1, sizeof(dp));
    return make_change((int) coins.size() - 1, amount, coins);
}

// -------- END --------

3) iterative_dp_solution

Let dp[idx][target] be the number of ways we can make target using coins from indices less than or equal to idx, inclusive. By definition, dp[n - 1][amount] is what we need to return. dp[idx][0] = 1 holds for all idx between 0 to n -1 as we can always make 0 in one way ( by not using any coin at all ). This is the base case of our solution.

Now let us focus on how to compute dp[idx , target]. We can make the amount target in two ways.

  • by using the coin at index idx: If we use the coin at index idx, our next goal would be to make (target - coins[idx]) by using the coins from indices between 0 to idx. Here coins[idx] is the denomination of the coin at index idx. There are dp[idx][target - coins[idx]] ways in total by definition. Notice that we did not update the parameter idx because we were allowed to use a coin as many times as we wanted.
  • by not using the coin at index idx: By definition, there are  dp[idx - 1][target] ways in total to do so.

If we combine the two cases, we get the following recurrence relation:

dp[idx][target] = (dp[idx - 1][target] + dp[idx][target-coins[idx]]) % 1000000007

Be careful to fill up the dp table in the right order. While computing a cell in the table, make sure that those cells who contribute to this cell have already been computed. In this problem incrementing idx from 0 to n - 1 and incrementing the target from 0 to amount works.

Time Complexity:

O(n * amount).

There are (n * amount) different possible states which we may need to compute. So the time complexity is equal to O(n * amount).

Auxiliary Space Used:

O(n*amount) space has been used for the dp table.

Space Complexity:

Space used for input: O(n).

Auxiliary space used: O(n * amount).

Space used for output: O(1).

So total space complexity: O(n * amount).


// -------- START --------

#define MOD         1000000007
#define MAXN        100
#define MAXVAL      10000


int dp[MAXN+3][MAXVAL+3];
// dp[idx][target] = number of ways we can make "target" using coins from indices less than or equal to "idx"

int number_of_ways(vector coins, int amount) {

    for(int idx = 0; idx < (int) coins.size(); idx++){
        for(int target = 0; target <= amount; target++){

            if(target == 0){
                dp[idx][0] = 1; // As we can make 0 in one way - by using no coin at all
            }
            else{

                // We have two options for the coin sitting in index "idx"

                // 1. We can decide to not use this coin to make the sum "target"
                if(idx > 0){
                    dp[idx][target] = dp[idx - 1][target];
                }

                // 2. We can use it as many times as we want
                if(target - coins[idx] >= 0){ // So that we do not access any negative index

                    // For every way in which we can make the sum (target - coins[idx]),
                    // we can make the sum equal to target by using the coin at index "idx"
                    dp[idx][target] = (dp[idx][target] + dp[idx][target - coins[idx]]) % MOD;
                }
            }
        }
    }

    return dp[(int) coins.size() - 1][amount];
}

// -------- END --------

4) iterative_dp_solution_with_memory_optimization

The dp table that we computed in our previous solution had a size of (n * amount). Let us call it the "complete dp table". The complete dp table can be thought of as a table with n rows and amount columns. In our solution, we will fill up the table row by row. Notice that, while computing any cell of a row, we only need the information from the immediate previous row. So we do not need to store all the rows of the complete dp table. Only the data of the immediate previous row and current row which we are computing needs to be stored. Our optimized dp table has 2 rows and amount columns. We will be cyclically using these two rows to compute our solution. While computing the rows, the data of the i-th row from the complete dp table will be stored in (i % 2)-th row of our optimized dp table. So whenever we are computing any row of the dp table, we will have the information of the previous row. For example, suppose we are trying to compute the dp table for the test case: coins = [ 9, 1, 8, 10, 3 ], value = 12.

The complete dp table looks as follows:

Now let us construct the optimized dp table. The 0th row can be computed without the help of any other row and the 1st row can be computed with the help of the 0-th row. So after computing the first two rows, our optimized dp table will look like:

At this stage, we do not need the information from the 0-th row. So we can overwrite this memory to store information about the 2nd row of the complete dp table.

Similarly in this stage, we can replace the information of the 1st row with the new information from the 3rd row of the complete dp table.

Finally, on the last iteration, the table will look like:

But can we do better? Turns out that we can discard one of the two rows. Let us focus on the recurrence relation:

dp[idx][target] = (dp[idx - 1][target] + dp[idx][target-coins[idx]])

Notice that any cell contributes only its value to the next row of the same column. In other words, when moving from one row to another, we add some other value over the already existing value of that column. For this reason, we can use a one-dimensional array of size amount and add to the existing array data while moving from one row to the next row.

Time Complexity:

O(n * amount).

Auxiliary Space Used:

O(amount) space has been used for the dp table.

Space Complexity:

Space used for input: O(n).

Auxiliary space used: O(amount).

Space used for output: O(1).

So total space complexity: O(n + amount).


// -------- START --------

#define MOD         1000000007
#define MAXN        100
#define MAXVAL      10000


int dp[2][MAXVAL+3];

/*
    Memory optimization idea:
    In this problem there can be O(n * amount) different states. So the dp table that we are computing should
    be of the size n * amount. Let us call this dp table of size n * amount as the "complete dp table".
    The complete dp table can be thought as a table having "n" rows and "amount" columns. In our solution, we
    will fill up the table row by row. Notice that, while computing any cell of a row, we only need the
    information from the immediate previous row. So we do not need to store all the rows of the complete dp
    table during computing the table. Only the data of the immediate previous row and current row needs to be
    stored.
    Our optimized dp table has 2 rows and "amount" columns. We will be cyclically using these two rows to
    compute our solution. While computing the rows, the data of the i-th row from the complete dp table will
    be stored in (i % 2)-th row of our optimized dp table.
*/

int number_of_ways(vector coins, int amount) {

    for(int idx = 0; idx < (int) coins.size(); idx++){
        for(int target = 0; target <= amount; target++){

            if(target == 0){
                dp[idx % 2][0] = 1; // As we can make 0 in one way - by using no coin at all
            }
            else{

                // We have two options for the coin sitting in index "idx"

                // 1. We can decide to not use this coin to make the sum "target"
                if(idx > 0){
                    dp[idx % 2][target] = dp[(idx - 1) % 2][target];
                }

                // 2. We can use it as many times as we want
                if(target - coins[idx] >= 0){ // So that we do not access any negative index

                    // For every way in which we can make the sum (target - coins[idx]),
                    // we can make the sum equal to target by using the coin at index "idx"
                    dp[idx % 2][target] = (dp[idx % 2][target] + dp[idx % 2][target - coins[idx]]) % MOD;
                }
            }
        }
    }

    return dp[((int) coins.size() - 1) % 2][amount];
}

// -------- END --------


Attend our Free Webinar on How to Nail Your Next Technical Interview

Recommended Posts

All Posts