In this post, solution to leetcode problem – 518, coin change II – is explained. Please refer to this link for detail problem description.
This is very similar to combination sum IV problem. The only difference is that the order doesn’t matter and this is essentially a subset problem with duplicates. Let’s see how we can approach the problem.
Brute Force
Exhaustively enumerate all subsets and check if it makes the amount. This will have exponential cost.
Optimized version
We can follow the similar approach as combination sum IV problem. The only difference is that order doesn’t matter and if you blindly add results from previous coins, you will end up counting the duplicate as you see in the diagram below.
In the above diagram, the recurrence relation is simply adding the results from previous amount with all the coin denominations. How can we avoid counting the duplicate? Instead of looking at all the coins for each amount, we can control how many coins each node has. For example, each node is responsible for keeping track of the number of coins for only one coin. Let’s look at the diagram below.
Now, it is not counting the duplicate and you just need to add up all the nodes with valid combinations to get the final result. The recurrence relation would be f(i, a) = sum(f(i-1, a – c*coins[i])) where i is coin index, a is amount, c is number of coins. The range for c is 0 to max coins. How do you calculate max coin? It is simply amount / coins[i]. As there are overlapping subproblems, we can use dynamic programming to solve this. For this, as there are two variables, we would need two dimensional array. row represents coin index and col represents amount. (you can change row/col if you want). What’s the base case? For the first column, when amount = 0, there is only one combination to make the amount – empty subset. For the first row, when no coins are used – I remember I said row is coin index, but since index makes problem slightly more difficult, let’s say row is ith coin that 0th coin means no coin, and the first coin is the first coin in coins – there isn’t any combination possible to make any amount. So everything is 0 except the first column. Although there are more optimizations possible, let’s take a look at the pseudo-code
table: 2d array of row (num coins + 1) col (amount + 1)
initialze first column to 1. everything else is 0
for i in 1 to n: // n is number of coins
for a in 1 to amount:
maxCoins = a / coins[i-1] // note that i is index of table. to access corresponding coin, need to subtract 1
// check all the possible number of coins can be included
for c in 0 to maxCoins:
table[i][a] += table[i-1][a - c*coins[i-1]]
return table[n][amount]Solution is very simple but look at the time complexity. We already have a 2D table and there is an additional for-loop for each cell in the table. Can we do better?
More optimized version
If you closely look at the code, we can eliminate the inner for-loop (c) while achieving the goal. Instead of checking possible number of coins in the for-loop, let’s look at from exclusion/inclusion point of view. At each amount and coin[i], we have a choice – exclude or include. If you exclude, then you check the next coin. If you include, you have another choice – exclude or include the same coin again.
With that, we have a better time complexity. Here is the code written in C++.
int change(int amount, vector<int>& coins) {
vector<vector<int>> table(coins.size()+1, vector<int>(amount+1, 0));
for (int i = 0; i <= coins.size(); ++i)
{
table[i][0] = 1;
}
for (int i = 1; i <= coins.size(); ++i)
{
for (int j = 1; j <= amount; ++j)
{
// exclude
table[i][j] = table[i-1][j];
// include
if (j >= coins[i-1])
{
table[i][j] += table[i][j-coins[i-1]];
}
}
}
return table[coins.size()][amount];
}Time complexity=O(n*amount) where n is length of coins and amount is initial amount. Space complexity=(n*amount) because we create 2D array of n*amount. We are very close but there is one more optimization we can achieve – space complexity. If you look at the all the update, exclude code at line 13 is completely unnecessary because after processing the row, next row can start exactly same as previous row. In addition to that, when you look at inclusion code at line 18, you only look at previous column because you are including the same coin!
It means that we only need a 1D array. Here is the C++ code.
int change(int amount, vector<int>& coins) {
vector<int> table(amount+1, 0);
table[0] = 1;
for (int i = 1; i <= coins.size(); ++i)
{
for (int j = 1; j <= amount; ++j)
{
if (j >= coins[i-1])
{
table[j] += table[j-coins[i-1]];
}
}
}
return table[amount];
}Time complexity is unchanged because you have to iterate all the coins with all the amount. However, we reduced the space complexity to O(amount).
