Coin Change

gistfile1.txt

//This problem appeared on that application that most of us saw for that sweet company that we might maybe want to work for.
//The problem is coin change and it goes like this:

// -- changePossibilities(amount,amount): Your quirky boss collects rare, old coins. They found out you're a programmer and asked you to solve something they've been wondering for a long time. 
// Write a function that, given an amount of money and an array of coin denominations, computes the number of ways to make the amount of money with coins of the available denominations. 

// Example: for amount=4 (4¢) and denominations=[1,2,3] (1¢, 2¢ and 3¢), your program would output 4—the number of ways to make 4¢ with those denominations: 

// 1¢, 1¢, 1¢, 1¢
// 1¢, 1¢, 2¢
// 1¢, 3¢
// 2¢, 2¢

Now, the problem is somewhat similar to the classic coin change problem, where you are given a array of denominations and a target, except your goal is to return the smallest possible combination of coints to achieve the target.

Now, the current problem at hand is very interesting, because we can solve it using memoization that we briefly touched during one of our REACTO pratises.

Here are some videos explaining the concept of how to arrive to the solution in an elegant and impressive way:
https://www.youtube.com/watch?v=PafJOaMzstY






//****SOLUTION*****
function changePossibilities(amount, denominations) {
  //values stored in the array will be the total count of combinations for the different amounts
  //each index in the array will correlate to the amount of money

  let combinations = []
  for (let i = 0; i <= amount; i++) {
    combinations[i] = 0;
  }
  combinations[0] = 1;

  for (let j = 0; j < denominations.length; j++) {
    let coin = denominations[j];

    for (let coinVal = coin; coinVal <= amount; coinVal++) {
      let remainderCoinVal = coinVal - coin;
      combinations[coinVal] += combinations[remainderCoinVal];
    }
  }
  return combinations[amount];
}

//Test cases:
//changePossibilities(4,[1,2,3]) //4
//changePossibilities(25, [25, 10, 5,1]) //13