Minimum Coins

Of all the possible coin combination, return the one with the fewest coins.

The problem

Write a function minChange that takes in an amount and an array of coins. The function should return the minimum number of coins required to create the amount. You may use each coin as many times as necessary. If it is not possible to create the amount, then return -1.

https://structy.net/problems/min-change

This one took me much longer than I thought, and I still had a sub-optimal solution. It was like the solution was just out of reach the whole time.. I was hung up on how to make the code return -1 if something wasn't possible. With that, I then struggled to know if a certain branch of the recursive tree was even possible. So I explored a way to return both if the branch led to a viable solution, and then the count alongside it. That I think was my third attempt, and I was still struggling. I decided I needed to simplify my approach, so I just wanted to find all possible combination, and from there I could .reduce to the smallest one.. not optimal, but a start... Here's what I managed to get before just looking at the solution:

const minChange = (amount, coins) => {
  if(amount === 0) {
    return 0;
  } else {
    const [possible, combos] = allCoinCombos(amount, coins);
    
    if(!possible) {
      return -1;
    } else {
      return combos.reduce((smallest, combo) => {
        return Math.min(smallest, combo.length);
      }, Number.MAX_SAFE_INTEGER);
    }
  }
};
 
const allCoinCombos = (amount, coins, used = []) => {
  if(amount < 0) {
    return [false, used];
  } else {
    const possibilities = [];
 
    coins.forEach((coin, index) => {
      if(amount - coin === 0) {
        possibilities.push(used.concat(coin));
      } else {
        const [possible, results] = allCoinCombos(
          amount - coin,
          coins.slice(index),
          used.concat(coin)
        );
 
        if(possible) {
          results.forEach((result) => {
            possibilities.push(result);
          })
        } 
      }
    });
 
    return [possibilities.length > 0, possibilities];
  }
};

I want to return to this and make it work better. I want to find how to memoize it, and maybe find the bottom up approach to it.

I guess the challenge is kind of nice, but it's definitely not fun. React is fun. Tailwind is fun. This is fucking boring and frustrating. But I guess you just eat the shit until you know it (at least memorize it) and then it doesn't taste so much like shit anymore.