I am trying to solve the famous Coin Change problem, below is the problem statement!!
You are given an integer array
coinsrepresenting coins of different denominations and an integeramountrepresenting a total amount of money.Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return
0.You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
Below are some examples to illustrate the problem.
Example 1:
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10]
Output: 1
Constraints:
1 <= coins.length <= 3001 <= coins[i] <= 5000- All the values of coins are unique.
0 <= amount <= 5000
On seeing this problem :-
My first line of attack was to quickly utilize the fact that at either step of coin selection for the given amount, either we can select the coin or not select it, that is skip it and move ahead to the next coin in the input coin array.
class Solution {
private int count = 0;
public int change( int amount, int[] coins) {
Integer[] arr = Arrays.stream( coins)
.boxed()
.sorted( Comparator.reverseOrder())
.toArray( Integer[]::new);
backtrack( arr, 0, amount);
return count;
}
private void backtrack( Integer[] coins, int index, int amount) {
if( index >= coins.length) {
if( amount == 0) {
++count;
}
}
else { // At every coin we have only two choices,
// either we take it or we skip it.
backtrack( coins, index + 1, amount);
// This is the skip case, we are incrementing the index
// by 1. And not taking that coin value into account
// by not decrementing the current coin value from amount.
if( coins[index] <= amount)
backtrack( coins, index, amount - coins[index]);
// We are taking that coin and subtracting the coin from the
// amount, not incrementing the index as the same coin can be
// considered multiple times, so as to be able to consider
// it multiple times we are not incrementing the index.
}
}
}
Even for a naive like me, it feels that my backtracking formulation for the above problem is correct. As I have carefully considered all the possible choices at a given coin selection step, either you take it, and decrement the amount, or skip it, when skipping you increment the index. Backtracking approach is giving TLE(Time Limit Exceeded), as is obvious as there are multiple recursive calls, and hence it is going to take exponential time, but if we cut down on the recursion, we can fix this TLE(Time Limit Exceeded) But when I am trying to convert this backtracking into top down memoized version, I am failing miserably.
Here is my attempt at that :-
class Solution {
private int count = 0;
public int change(int amount, int[] coins) {
int[] memo = new int[amount + 1];
Arrays.fill( memo, -1);
backtrack( coins, 0, memo, amount);
System.out.println( "The content of the array is "
+ Arrays.toString(memo));
return memo[amount];
}
private void backtrack( int[] coins, int index, int[] memo, int amount) {
if (index >= coins.length) {
if (amount == 0) {
++count;
return;
}
} else if (memo[amount] != -1){
return;
} else {
backtrack( coins, index + 1, memo, amount);
if (amount <= coins[index])
backtrack( coins, index + 1, memo, amount - coins[index]);
System.out.println( "The value of the count is ---> "
+ count
+ " and the value of the index is " + index);
System.out.println( "The content of the array in backtrack is "
+ Arrays.toString( memo));
memo[amount] += count;
}
}
}
What I intend from this code that it should fill the memo array with the corresponding count value, I want the count to be a global variable and the backtracking method should be returning void, as its return type.
With this template can I be able to fix my code to return the correct value for the amount? So I basically I want to know with minimum changes in the overall program layout can I fix this issue and get the correct result?
I only need to understand that once I have the backtracking approach with me, how to proceed from there to the memoized top down one and then to the bottom up approach, eventually.
The approach will not work, for several reasons, including:
count is global, and although it accumulates matches correctly at first, it will cause wrong solutions once backtracking has occurred and alternative paths are visited: in those paths, the value of count -- having results from other paths that split off at an earlier index -- is not correct.
When memo[amount] is found to be different from -1, no further recursion occurs: this is good, but it is not good that these possibilities are not counted on top of what you already had: if there are two different ways to reach a partial amount, then the number of ways to get from there to the final goal should be counted twice -- once for each alternative.
When memo[amount] gets its first count added to it, it was -1, so one count is lost.
memo is never used to help define other memo entries, yet this is one of the goals of memoization. In your code memo serves like a visited flag, but memoization should be used to retrieve a result that is then used to resolve another subproblem.
The second recursive call gets index + 1, but it should get index, because a coin could be used more than once.
if(amount <= coins[index]) is the wrong condition. This should be >=.
With recursion you should attempt to solve a smaller -- isolated problem. So a global count is out of the question. Given an index and an amount, the recursive call should solve the problem "how many possibilities exist to consume that amount with the coins available from this index onwards". This count should be the return value of the recursive function.
Memoization should distinguish between the unique states of the subproblems. In this case the recursive call gets two constraints: the still available coins (index) and the (remaining) amount to cover for. So your memo needs two dimensions, not one.
Here is the adapted code:
class Solution {
public int change(int amount, int[] coins) {
int[][] memo = new int[amount + 1][coins.length]; // Two dimensions
for (var row : memo) {
Arrays.fill(row, -1);
}
return backtrack(coins, 0, memo, amount);
}
private int backtrack(int[] coins, int index, int[][] memo, int amount){
if (amount == 0) { // At any time we're interested in a match
return 1; // Found a solution. Callers will add this to their own counts
}
if (index >= coins.length || amount < 0) {
return 0; // No further matches possible without backtracking
}
if (memo[amount][index] == -1) {
// Don't take this coin or take it one or more times:
memo[amount][index] = backtrack(coins, index + 1, memo, amount)
+ backtrack(coins, index, memo, amount - coins[index]);
}
return memo[amount][index];
}
}