minimum coin change problem with recursion and memoization in javascript

The Problem is to find the minimum number of coins required for constructing a sum. This is a classic optimization problem and i will show how to use recursion to solve the problem and memoization to optimize the solution.

In this problem, you are given a set of coins and a target sum, and you are expected to construct the target sum using any combination of the given set. You may end up with more than one way to construct the target sum but are expected to return the result with the minimal combination.

For example given the set [5, 3, 4] and a target sum of 10 for instance, the combination [3, 3, 4] will surely sum up to the target sum 10, but is not the result with the minimal combination; rather, [5, 5] will be the result with the minimal combination in this case.

What i really seek to show you in this post is to show you a general trick that you can use in optimization problems such as this one to solve dynamic programming problem generally using recursion.

First for any dynamic programming problem such as this, always make sure to use a tree diagram to see clearly what’s going on – this is the trick/key to solving the problem. Let’s look at the break down of this problem using the tree diagram below:

Fig 1

They points to deduce from this tree are as follows:

  • The target sum is the root node
  • The values of the set are continuously subtracted from the target sum at each level as far as the balance is up to the least value of the set.
  • The balance after subtracting a value of the set from the target sum is the new target sum.
  • Any path from the root node 10 that reaches the base case 0, the values of the set subtracted from the target sum along that path up to the base case 0 will definitely sum up to the target sum 10.
  • Any of the path from the root node 10 to the base case 0 is an option for our solution but may not necessarily be the path with the minimal combination of our set values. For instance the first path that we can find in our diagram that reaches 0 has the combination [5, 5] because we subtracted 5 from 10 in the first level, and then we subtracted another 5 from the new target sum 5 to get to 0. The second path that gets to 0 from the root node has the combination [3, 3, 4], the third path has [3, 4, 3] and the last path has the combination [4, 3, 3]; but the path with the optimal solution (i.e with the least combination) is the one with [5, 5], so our program should return that one.
  • Even though i have not shown it in the tree diagram above, if we try subtracting any of the value of our given set from a target sum lower than the least value in our set, we get a negative value. For instance, if we try to subtract say 3 from 2, we get a negative value. We will use this condition to construct our first base case. If (target sum < 0) return null.
  • If target sum gets to 0, return an empty array – this is our second base case.

Let’s look at the first path with the combination of [5, 5] for instance, at the base case case 0, let’s start by returning an empty array to the calling function (this is our second base case). As we return the empty array to the calling function, we then include the value of the set that was subtracted from the target sum (which is stored in the call stack) to the empty array. This is how we will bubble our way to the root node, including the value of our set that was subtracted from the target sum. So first we return an empty array from the base case 0 to our calling function where the target sum is 5 – then we add the subtracted value 5 to the returned empty array. So at this level what we have is [5], then we do the same thing as our recursive function bactracks from there to the calling function at which point the target sum was 10 – again we add the subtracted value 5 to our array of [5]; so our array is now [5, 5]; we do this same thing for all of the paths where our base case is 0, adding the subtracted values to the initial empty array as we backtrack our way all the way to the root node.

So the question is: how do we get only the combination with the minimal set values that formed our target sum? we must then write our algorithm in such a way that it returns the path with the minimal combination. What we can do is to compare all of our branches in the tree (i.e compare each recursive call) and maintain an array of the combination with the minimum set values per recursive call.

The Solution Algorithm in Javascript (Brute Force Approach)

The solution is fully commented so that as you read through each line of code, you can compare the comment with what has been explained earlier to fit all things together.

const minimumCoin = (TargetSum, Coins) => {
  if(TargetSum < 0) return null;//first base case
  if(TargetSum === 0) return [];//second base case
  
  let minCoinArr = null;//Initialize this variable for maintaining an array of the combination with the minimum set values per recursive call
  
  for(let eachCoin of Coins){//branch (look at our tree) for each coin in our given coin set with which we are to form the target sum
    const newTargetSum = TargetSum - eachCoin;//subtract each value in our given coins set from the target sum to get the new target sum for the next level
    const result = minimumCoin(newTargetSum, Coins);//make each recursive call(either of our base case is returned initially depending on the value of the target sum at the time of calling)
    if(result !== null){
      const resultingArr = [ ...result, eachCoin ];//copy array values of result from previous recursive call forward, including the value of the branch where you are dealing with at the time
      if(minCoinArr === null || resultingArr.length < minCoinArr.length){//maintain an array of the combination with the minimum set values per recursive call
        minCoinArr = resultingArr;
      }
    }
  }
  return minCoinArr;//after everything, return the minimum coin array
}

Now what i want you to do is to test that code with several inputs. You can start with the one below:

console.log(minimumCoin(10, [5,3,4]));//expected output is [5,5]

10 is the target sum and [5, 3, 4] is the set of coins with which you are to find the minimum combination of the set values that forms the target sum. This one runs pretty fast and gives the expected output [5, 5]. Let’s try with all of this input at once:

console.log(minimumCoin(5, [1,2,5]));//expected output [5]
console.log(minimumCoin(10, [1,2,5]));//expected output [5,5]
console.log(minimumCoin(12, [1,2,5]));//expected output [5,5,2]
console.log(minimumCoin(12, [1,3,5]));//expected output [5,5,1,1]
console.log(minimumCoin(100, [1,2,5,25]));//expected output [25,25,25,25]

So you should notice that the first 4 scenarios ran fast but the last one is probably still running – this is not desirable.

Time Complexity for Brute Force Approach

So very simply, i am branching for each of the coin values in our set n1 times at level 0. Imagine that at the worst case scenario our set of n values contained only values of 1, meaning that we had to subtract only 1 from the target sum for each recursive call from the root node all the way to the base case of 0), so at level 1, we would have branched for n2 at level 1, and nm for the last level – i.e our base case level; see diagram below for an example with target sum 4 for the purpose of this explanation.

Fig 2

Also the line of code shown below in our solution algorithm

const resultingArr = [ ...result, eachCoin ];//copy array values of result from previous recursive call forward, including the value of the branch where you are dealing with at the time

does a copy in linear time (in the worst case of say a set n containing only values of 1’s and a target sum of m, then this should copy m time – refer to our tree), so our final time complexity for this brute force algorithm is actually O(nm * m). This time complexity is not good at all and is what is causing our last test case to delay to display its output. The key to solving this problem is apply memoization to the brute force solution.

The Solution Algorithm including Memoization

Memoization is really about storing the target sum and the values of the set that formed that target sum for each recursive call in an array or object (all the way from the root node to the leaf nodes). What that means is that we do not need to recalculate a target sum that has been calculated before in any part of our tree; instead we first check our object to see if that value is stored in there; if stored, then we simply return the value that is stored in there and avoid further recursive calls.

To fully understand what’s going on, take a look at Fig 2 above, what you will notice is that target sum repeat at some of the nodes – meaning that you have to make recursive calls for values of target sum that you have already calculated. For instance at level 1, i can see the value 3 repeating 3 times, if we have captured the minimumCoins for this target sum 3 the first time it was encountered, then we would not have need to recalculate it the second and third time – we would just look up the stored values of the minimumCoins and return that, thereby avoiding all the recursive calls below that point.

For our particular case, we will use an object called memo and a key called TargetSum for storing calculated values of minimumCoins. There are only 3 places i have made changes to the code.

  1. I have initialized an empty memo object as a parameter in our minimumCoin function definition
  2. I have passed that memo object as a parameter in our recursive calls
  3. I have assigned values of minimumCoin to the memo object so that the do not need to be recalculated in future recursive calls.
const minimumCoin = (TargetSum, Coins, memo={}) => {
  if(TargetSum in memo) return memo[TargetSum];
  if(TargetSum < 0) return null;//first base case
  if(TargetSum === 0) return [];//second base case
  
  let minCoinArr = null;//Initialize this variable for maintaining an array of the combination with the minimum set values per recursive call
  
  for(let eachCoin of Coins){//branch (look at our tree) for each coin in our given coin set with which we are to form the target sum
    const newTargetSum = TargetSum - eachCoin;//subtract each value in our given coins set from the target sum to get the new target sum for the next level
    const result = minimumCoin(newTargetSum, Coins, memo);//make each recursive call(either of our base case is returned initially depending on the value of the target sum at the time of calling)
    if(result !== null){
      const resultingArr = [ ...result, eachCoin ];//copy array values of result from previous recursive call forward, including the value of the branch where you are dealing with at the time
      if(minCoinArr === null || resultingArr.length < minCoinArr.length){//maintain an array of the combination with the minimum set values per recursive call
        minCoinArr = resultingArr;
      }
    }
  }
  memo[TargetSum] = minCoinArr;
  return minCoinArr;//after everything, return the minimum coin array
}

console.log(minimumCoin(5, [1,2,5]));//expected output [5]
console.log(minimumCoin(10, [1,2,5]));//expected output [5,5]
console.log(minimumCoin(12, [1,2,5]));//expected output [5,5,2]
console.log(minimumCoin(12, [1,3,5]));//expected output [5,5,1,1]
console.log(minimumCoin(100, [1,2,5,25]));//expected output [25,25,25,25]

You should notice how fast it is for the last test case which previously took overly long to finish.

Time Complexity for Memoized Solution

Fig 3

With memoization Fig 2 has been reduced to Fig 3; why? Because the first time target sum 3, 2, 1 are calculated, they minimumCoins are stored in the memo object so that when the recursive call is made in the second and third branches, more recursive calls are truncated because the minimunCoins are fetched directly from the memo object.

The time complexity has therefore been reduced so far to O(n * m) – n for our input set multiplied by the height of our new tree denoted by m. Then we have to do the additional work of copying the subtracted values into our resultingArr array and so the final time complexity will be: O(n * m * m) or O(nm2).

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

You May Also Like