Minimum coin change problem using recursion in JavaScript

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1: Input: coins = [1,2], amount = 4 Output: 2 Explanation: 4 =
2 + 2,4=1+1+2

The recursion formual for coin change as below

coinchange(j,a)={,if j<00,if j =01+min(i=knc[jai])if j >1 coinchange(j,a) = \begin{cases} \infty, & \text{if $j$<0} \\ 0, & \text{if $j$ =0} \\ 1+\min(\sum_{i=k}^n c[j-a_i]) & \text{if $j$ >1} \end{cases}

function coin_change(amount) {
  // if remaining  coin is zero return
  if (amount == 0) return 0
  // if coin is negative return some large value
  if (amount < 0) return Infinity
  let ans = Infinity
  for (const coin of coins)
    ans = Math.min(
      1 + coin_change(amount - coin)
  return ans

Recursion Tree

This article only show you how to write recursive program. I know this is not optimized way to write coin change problem{alertError}

Post a Comment

Please do not post any spam link in the comment box😊

Previous Post Next Post

Blog ads