Coin change problem all combinations in javascript

In this solution, we will be exploring the option of going through all combination to count the number of ways or number of solutions for coin change problem. They technique shown here is applicable for any variation of the coin change problem. You can look here afterward to see a variation of the coin change problem i.e to find the minimum number of coins that form a target sum in javascript.

This is a classic example of an algorithm problem that we can solve using recursion and backtracking, as well as dynamic programming (i.e crafting a brute force solution to derive at a correct solution and then applying memoization to optimize the speed of the solution).

The Problem is to count the total number of solutions for all combination of a set of coins that can form or construct a given target sum.

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, [5, 5] will also sum up to the target sum of 10, [3, 4, 3] will also yield same target sum and [4, 3, 3] also.

As i have stressed elsewhere, always start a recursive or dynamic programming problem with a a tree diagram so that you can see first hand all that’s going on. So for the problem we are trying to solve here, i will start with this tree.

To solve this problem, use the idea that if you continue in each recursive step to subtract any of the value of the given coin set from the target sum, you will end up having 0 as some of the base cases, and any base case that gets to 0, all the values subtracted by each of the recursive call on that path will definitely sum up to the target sum, with that; you’ve found a possible solution. So looking at our tree above, you find 4 different base cases that ends in 0 and their path have the following values that was subtracted each in each recursive call: [5, 5], [3, 3, 4], [3, 4, 3] and [4, 3, 3] ; all of this combinations sum up to our given target sum.

Our solution algorithm is expected to return the output 4, since there are 4 different ways to construct the target sum 4.

To solve the problem, we have two base cases:

  1. When our target sum is 0, and
  2. When our target sum has a negative value.

Our target sum can have a negative value due to the fact that such a figure like 2 or 1 (as can be seen in the tree), when subtracted by any of the values of our set [5, 3, 4] will result in a negative value.

For our base cases,

  • when target sum is 0, return 1, and
  • when target sum < 0, return 0.

The solution algorithm (brute force – without optimization)

<script>
		const Coin = (TargetSum, Coins) => {
		  if(TargetSum < 0) return 0;//first base case
		  if(TargetSum === 0) return 1;//second base case
		  
		  var cnt = 0;//Initialize this variable for storing count of ways to combine our coins set values to construct our target sum
		  
		  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
			var result = Coin(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)
			cnt += result;//increment count of ways to combine our coins set values to construct the given target sum
		  }
		  return cnt;//after everything, return the count of ways to combine our coins set value to construct our target sum
		}

		console.log(Coin(5, [1,2,5]));//expected output 9
		console.log(Coin(10, [5,3,4]));//expected output 4
		console.log(Coin(12, [1,2,5]));//expected output 372
		console.log(Coin(12, [1,3,5]));//expected output 116
		console.log(Coin(100, [1,2,5,25]));//expected output 9.12048770173567e+22
	</script>

You may have noticed that the last test case is taking a very long time to return its result because the code is yet to be optimized. To understand the cause of the problem, look under the heading: The Solution Algorithm including Memoization here.

The optimized solution

<script>
		const Coin = (TargetSum, Coins, memo={}) => {
		  if(TargetSum in memo) return memo[TargetSum];// return the value that is stored in memo (if stored) and avoid further recursive calls
		  if(TargetSum < 0) return 0;//first base case
		  if(TargetSum === 0) return 1;//second base case
		  
		  var cnt = 0;//Initialize this variable for storing count of ways to combine our coins set values to construct our target sum
		  
		  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
			var result = Coin(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)
			cnt += result;
			memo[TargetSum] = cnt;//store calculated result in memo object
		  }
		  return cnt;//after everything, return the count of ways to combine our coins set value to construct our target sum
		}

		console.log(Coin(5, [1,2,5]));//expected output 9
		console.log(Coin(10, [5,3,4]));//expected output 4
		console.log(Coin(12, [1,2,5]));//expected output 372
		console.log(Coin(12, [1,3,5]));//expected output 116
		console.log(Coin(100, [1,2,5,25]));//expected output 9.12048770173567e+22
	</script>
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