What is coins sums?

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.

Example

Suppose you are given coins with the values 11¢, 22¢, and 55¢. How many ways can you make 55¢ using any combination of the coins above?

The answer is 44. There are 44 ways of making a total of 55¢:

  • 11¢, 11¢, 11¢, 11¢, 11¢
  • 11¢, 11¢, 11¢, 22¢
  • 11¢, 22¢, 22¢
  • 55¢

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 55¢ with 11¢, 22¢, and 55¢. The table will look like this:

svg viewer

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 00¢.

The only way to make 00¢ is to not pick up any coins​. Therefore, we fill the first column with 11s.

svg viewer

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

svg viewer

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

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

svg viewer

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

svg viewer

But, for a 22¢ sum, there are 22 ways: either choose two 11¢ coins or one 22¢ coin.

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

  • the number of ways of getting 22¢ without the 22¢ coin (green).
  • the number of ways of getting 22¢ with the 22¢ coin (sum - coin) (orange).
svg viewer

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.

svg viewer

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 O(T∗N)O(T*N), where TT is the total sum and NN is the number of coins.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved