6
$\begingroup$

The Coin Change problem is stated as:

Given an integer array coins[ ] of size N representing different denominations of currency and an integer sum, find the number of ways you can make sum by using different combinations from coins[ ].
Note: Assume that you have an infinite supply of each type of coin.

So for example using coins {1, 2, 3} and a desired sums of 3, yields combinations (1,1,1), (1,2) and (3).

This problem can be solved using dynamic programming where the idea is to iteratively count the the number of combinations that can amount to a partial sum:

    std::vector<int> combinations_to_consume_sum(sum + 1, 0);
    combinations_to_consume_sum[0] = 1; // if we got here, we consumed everything using a single coin
               
    for (int i = 0; i < N; ++i) // go through each coin
    {
        int coin = coins[i];
        
        for (int partial_sum = 1; partial_sum <= sum; ++partial_sum)
        {
            int leftover_sum = partial_sum - coin;
            
            if (leftover_sum >= 0)
            {
                combinations_to_consume_sum[partial_sum] += combinations_to_consume_sum[leftover_sum];
            }
        }
    }
    return combinations_to_consume_sum[sum];

This is a working solution. However, if I swap the order of the 2 nested loops, the algorithm is no longer correct:

    for (int partial_sum = 1; partial_sum <= sum; ++partial_sum) 
    {
        for (int i = 0; i < N; ++i)
        {
            int coin = coins[i];
            
            int leftover_sum = partial_sum - coin;
            
            if (leftover_sum >= 0)
            {
                combinations_to_consume_sum[partial_sum] += combinations_to_consume_sum[leftover_sum];
            }
        }
    }
    return combinations_to_consume_sum[sum];

Can someone offer an explanation as to why this approach only works when using a 'coins first' approach?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ When nested loops update the same datum multiple times, a different nesting of the loops will make a difference, more often than not. $\endgroup$
    – John L.
    Oct 2, 2022 at 1:41
  • $\begingroup$ I find it pretty weird to start the loop incrementing partial_sum (in the first solution) at value 1, but then decide to do nothing until partial_sum>=coin holds. You might as well start with partial_sum=coin. $\endgroup$
    – Marc van Leeuwen
    Oct 3, 2022 at 11:57
  • $\begingroup$ I know that, I just wanted the 2 solutions to be as identical as possible. $\endgroup$
    – Elad Maimoni
    Oct 3, 2022 at 12:04

2 Answers 2

Reset to default
11
$\begingroup$

In the second solution you are overcounting the number of combinations. In fact you are counting the of ways to choose an ordered list of coins that sums to sum.

For example suppose that you have coins of values $1$ and $2$.

  • There is only one way to obtain a sum of $0$, namely using no coins and the algorithm computes this correctly.
  • There is only one way to obtain a sum of $1$, and the algorithm computes this correctly (by "using" coin $1$ and looking at the number of ways to use $0$ coins to obtain a sum of $0$).
  • There are two ways to obtain a sum of $2$, namely using two $1$ coins or a single $2$ coin. The algorithm also happens to compute this correctly by summing the $1$ way to obtain a sum of $1$ (when the $1$ coins is used) with the $1$ way to obtain a sum of $0$ (when the two coin is used).
  • There are two ways to obtain a sum of $3$, namely using three $1$ coins or a $1$ coin and a $2$ coin. The algorithm fails here as it considers:
    • The two ways to obtain a sum of $2$ (after the $1$ coin is used). These are $(1,1)$ and $(2)$. This case accounts for the following ways to obtain a sum of $3$: $(1,1,1)$, and $(1,2)$.
    • The one way to obtain a sum of $1$ (after the $2$ coin is used). This is $(1)$. This case accounts for the following way to obtain a sum of $3$: $(2,1)$.

As you can see, the option of using a $2$ coin and a $1$ coin is counted twice (in the two different possible orders).

Improve this answer
$\endgroup$
3
  • $\begingroup$ I actually think I understand why the wrong method fails, But what I don't exactly get is how the correct method avoids counting all the permutations of the same combination. It looks the same to me. $\endgroup$
    – Elad Maimoni
    Oct 1, 2022 at 20:49
  • 3
    $\begingroup$ Consider the first approach. Focus on the generic $i$-th iteration of the outer loop, when you are the $i$-th coin having some value $x$. When you look at a partial sum $s$ (in the inner loop) you are accounting for all combinations that sum to $s$ and use 1) at least one coin with value $x$ and 2) no occurrences of the $j$-th coin for all $j>i$. Notice this last property! The number of combinations that satisfy these constraints is exactly the value of combinations_to_consume_sum[leftover_sum] (at this point). $\endgroup$
    – Steven
    Oct 1, 2022 at 21:04
  • 1
    $\begingroup$ Each combination of coins $(c_1, c_2, \dots, c_k)$ that sums to some value $s$ is accounted for exactly once, namely when the outer loop considers the coin with value $x$ where $x$ is the maximum of $c_1, c_2, \dots, c_k$ and the inner loop considers $s$. $\endgroup$
    – Steven
    Oct 1, 2022 at 21:06
6
$\begingroup$

Why is the working solution correct?

First things first. Important things first. Let us understand why the working solution is correct first instead of finding where the wrong solution goes wrong.

Here is a solution that is easier to understand.

Introduce a 2-dimensional variable combinations so that combinations[i+1][s] will be the number of combinations of coins with values in coins[0..i] that sum up to s.

 1    std::vector<vector<int>> combinations(N, vector<int> (sum + 1, 0));
 2    combinations[0][0] = 1; //no coin. zero sum. This is one combination.
 3                  
 4    for (int i = 0; i < N; ++i) // go through each coin
 5    {
 7        int coin = coins[i];
 8          
 9        for (int partial_sum = 1; partial_sum <= sum; ++partial_sum)
10        {
11            int leftover_sum = partial_sum - coin;
12                
13            if (leftover_sum >= 0)
14            {
15                combinations[i + 1][partial_sum] = 
                          combinations[i][partial_sum] 
                          + combinations[i + 1][leftover_sum];
16            }
17        }
18    }
19    return combinations_to_consume_sum[sum];

A combination of coins from coins[0..i] that sum to partial_sum

  • either does not contain coins[i], which means it is a combination of coins with values in coins[0..(i-1)] that sum to partial_sum
  • or contain coins[i], which means it is
    • a coin with value coins[i]
    • together with a combination of coins with values in coins[0..i] that sum to partial_sum - coins[i], which is stored in leftover_sum.

Hence we have the recurrence relation on line 15 of the code above. Also note that at the moment when we run line 15, all terms on the right-hand side has been settled:

  • the term combinations[i][partial_sum] is settled since i < i + 1
  • the term combinations[i + 1][leftover_sum] is settled since 0 <= leftover_sum < partial_sum.

Hence after line 15, combinations[i + 1][partial_sum] is settled.

The working solution in the question is the condensed version of the solution above. Instead of a two-dimensional combinations, we use a one-dimensional vector combinations_to_consume_sum, which functions exactly the same.

What is computed by the incorrect solution?

Steven's answer explains why the incorrect solution is wrong. Basically, it can count the same combination more than once. For example, when coins is {2, 3} and sum is 5, it will count $(2, 3)$ once and $(3,2)$ once, although they are the same combination.

In fact, the incorrect solution computes the number of different sequences of coins whose values are in coins and whose sum is sum. When there is at least one combination of different values that sum to sum, the incorrect solution will return a number that is larger than the number of combinations wanted.

Two exercises

  1. If the values in coins are not necessarily different, explain what is computed by the first solution in the question. What is computed by the second solution?
  1. What is computed by the first solution in the question if for (int partial_sum = 1; partial_sum <= sum; ++partial_sum) is replaced by for (int partial_sum = sum; partial_sum >= 1; --partial_sum)? What about the second solution?
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ line 9 can be replaced by ` for (int partial_sum = coin; partial_sum <= sum; ++partial_sum)`. Then line 13, 14 and 16 can be removed. $\endgroup$
    – John L.
    Oct 2, 2022 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.