What is coins sums?
Educative Answers TeamCoin 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.
Example
Suppose you are given coins with the values ¢, ¢, and ¢. How many ways can you make ¢ using any combination of the coins above?
The answer is . There are ways of making a total of ¢:
- ¢, ¢, ¢, ¢, ¢
- ¢, ¢, ¢, ¢
- ¢, ¢, ¢
- ¢
Explanation
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 ¢ with ¢, ¢, and ¢. 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 ¢.
The only way to make ¢ is to not pick up any coins. Therefore, we fill the first column with s.
Now, let’s fill the rest of the first row. There is no way you can make ¢ using no coins (∅). Similarly, you can not make ¢, and so on, using no coins; thus, there are zero ways of doing this.
Moving on to the next row, there is only way of making a sum of ¢ using the ¢ coin.
The only way to make the sum of ¢ is by choosing all the ¢ coins. We will add this in the second row.
In the third row, the only way to get a sum of ¢ is by choosing a ¢ coin. So, we will add this in the third row.
But, for a ¢ sum, there are ways: either choose two ¢ coins or one ¢ coin.
You can infer this from the table. The ¢ value is the sum of two values already in the table:
- the number of ways of getting ¢ without the ¢ coin (green).
- the number of ways of getting ¢ with the ¢ 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.
Code
#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 , where is the total sum and is the number of coins.
RELATED TAGS
View all Courses
