If you're preparing for a technical interview at FAANG, you must practice the coin change problem. The goal of this problem is to find the number coin combinations that can make a given amount. We will solve the coin change problem using 4 solutions and also tell you the time and space complexity for each.

Number Of Ways To Make Change Problem Statement

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 an infinite supply of coins of every denomination.

Example

{
"coins ": [1, 2, 3],
"amount": 3
}

Output:

3

The three ways are:

1. Use the coin with denomination 1 three times.
2. Use the coin with denomination 3 once.
3. Use the coin with denomination 2 once and coin with denomination 1 once.

Notes

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

Constraints:

• 1 <= total number of denominations <= 10²
• 1 <= denomination of a coin <= 10⁴
• 1 <= amount to be expressed <= 10⁴

We have provided the following solutions:

• Brute force solution using recursion
• 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.

Number Of Ways To Make Change Solution 1: Recursive

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 2ⁿ - 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 2ⁿ - 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

O(n + amount).

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).

Code For Number Of Ways To Make Change Solution 1: Recursive

/*
Asymptotic complexity in terms of \`n\` = size of the input list and \`amount\`:
* Time: O(2^n).
* Auxiliary space: O(n + amount).
* Total space: O(n + amount).
*/

#define MOD 1000000007

int make_change(int idx, int target, vector<int> &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;
        }
    }

    // We have two options for the coin sitting at 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<int> &coins, int amount) {
    return make_change((int)coins.size() - 1, amount, coins);
}

Number Of Ways To Make Change Solution 2: Dp Recursion 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 three 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

O(n * amount).

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).

Code For Number Of Ways To Make Change Solution 2: Dp Recursion Memoization

/*
Asymptotic complexity in terms of \`n\` = size of the input list and \`amount\`:
* Time: O(n * amount).
* Auxiliary space: O(n * amount).
* Total space: O(n * amount).
*/

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

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

int make_change(int idx, int target, vector<int> &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;
        }
    }

    // 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<int> &coins, int amount) {
    memset(dp, -1, sizeof(dp));
    return make_change((int)coins.size() - 1, amount, coins);
}

Number Of Ways To Make Change Solution 3: Iterative Dp

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 states that we may need to compute, and we compute each in constant time.

Auxiliary Space Used

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

Space Complexity

O(n * amount).

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).

Code For Number Of Ways To Make Change Solution 3: Iterative Dp

/*
Asymptotic complexity in terms of \`n\` = size of the input list and \`amount\`:
* Time: O(n * amount).
* Auxiliary space: O(n * amount).
* Total space: O(n * amount).
*/

#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<int> &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];
}

Number Of Ways To Make Change Solution 4: Iterative Dp Memory Optimized

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:

1   0   0   0   0   0   0   0   0   1   0   0   0
1   1   1   1   1   1   1   1   1   2   2   2   2
1   1   1   1   1   1   1   1   2   3   3   3   3
1   1   1   1   1   1   1   1   2   3   4   4   4
1   1   1   2   2   2   3   3   4   6   7   8   10

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:

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

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.

1   1   1   1   1   1   1   1   2   3   3   3   3
1   1   1   1   1   1   1   1   1   2   2   2   2

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.

1   1   1   1   1   1   1   1   2   3   3   3   3
1   1   1   1   1   1   1   1   2   3   4   4   4

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

1   1   1   2   2   2   3   3   4   6   7   8   10
1   1   1   1   1   1   1   1   2   3   4   4   4

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

O(n + amount).

Space used for input: O(n).

Auxiliary space used: O(amount).

Space used for output: O(1).

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

Code For Number Of Ways To Make Change Solution 4: Iterative Dp Memory Optimized

/*
Asymptotic complexity in terms of \`n\` = size of the input list and \`amount\`:
* Time: O(n * amount).
* Auxiliary space: O(amount).
* Total space: O(n + amount).
*/

#define MOD 1000000007
#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<int> &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];
}

We hope that these solutions to the coin change problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.