Trusted answers to developer questions

Educative Answers Team

**Coin sums**, also known as **coin change**, is a famous dynamic programming problem. Given a total sum and a set of coins, you are asked about the number of ways you can make the total using any number of those coins.

Suppose you are given coins with the values $1$¢, $2$¢, and $5$¢. How many ways can you make $5$¢ using any combination of the coins above?

The answer is $4$. There are $4$ ways of making a total of $5$¢:

- $1$¢, $1$¢, $1$¢, $1$¢, $1$¢
- $1$¢, $1$¢, $1$¢, $2$¢
- $1$¢, $2$¢, $2$¢
- $5$¢

With every dynamic programming problem, we first break down the problem into sub-problems and build a table.

We will use the above example of making a total of $5$¢ with $1$¢, $2$¢, and $5$¢. The table will look like this:

Each entry in the table is the *number of ways that you can make the total sum using the available coins.*

Let’s fill the table starting with the first column, sum of $0$¢.

The only way to make $0$¢ is to not pick up any coins. Therefore, we fill the first column with $1$s.

Now, let’s fill the rest of the first row. There is no way you can make $1$¢ using no coins (**∅**). Similarly, you can not make $2$¢, and so on, using no coins; thus, there are zero ways of doing this.

Moving on to the next row, there is only $1$ way of making a sum of $1$¢ using the $1$¢ coin.

The only way to make the sum of $2$¢ is by choosing all the $1$¢ coins. We will add this in the second row.

In the third row, the only way to get a sum of $1$¢ is by choosing a $1$¢ coin. So, we will add this in the third row.

But, for a $2$¢ sum, there are $2$ ways: either choose two $1$¢ coins or one $2$¢ coin.

You can infer this from the table. The $2$¢ value is the sum of two values already in the table:

- the number of ways of getting $2$¢ without the $2$¢ coin (green).
- the number of ways of getting $2$¢ with the $2$¢ coin (sum - coin) (orange).

We will continue filling in the table using the above rule to get the following result. The last entry in the table is our answer.

#include <iostream> using namespace std; int coinSums(int coins[], int N, int T) { // We build a table with size N x T + 1 // + 1 since we add a column for the total sum of 0 int table[N][T + 1]; // Filling the entries for T = 0 case // Only 1 way for having a total of 0 for (int i = 0; i < N; i++) table[i][0] = 1; // Fill rest of the table entries for (int i = 0; i < N; i++) // for each row (available coins) { for (int j = 1; j < T + 1; j++) // for each column (total sums) { // Number of ways with the coin: coins[j] int withNewCoin = (j - coins[i] >= 0) ? table[i][j - coins[i]] : 0; // Number of ways without the coin: coins[j] int withoutNewCoin = (i >= 1) ? table[i - 1][j] : 0; // total number of ways table[i][j] = withNewCoin + withoutNewCoin; } } // The last entry is the answer return table[N - 1][T]; } int main() { int T = 5; // total int N = 3; // number of coins int coins[] = {1, 2, 5}; // array of coins cout << coinSums(coins, N, T); return 0; }

Both the time and space complexity for the above algorithm is $O(T*N)$, where $T$ is the total sum and $N$ is the number of coins.

RELATED TAGS

Copyright ©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses