JS solutions to the "coin combinations" interview puzzle

Published on Oct 10, 2022 in JavaScript

"Given an array of coins and a target amount, return all combinations of coins that add up to the amount, or an empty array if no such combinations exist."

Initial naive solution

Find all possible coin combinations.
- I have a separate post for that: Generating array permutations of all lengths in JS.
Filter out the combinations whose sum doesn't match the target amount.

Getting all combinations

const coins = [1, 2, 1, 5, 5, 10]
const amount = 12

const getCoinCombinations = (coins, amount) =>
  getCombinations(coins).filter((combo) => sum(combo) === amount)

const sum = (numbers) => numbers.reduce((a, b) => a + b, 0)

// Via https://mtsknn.fi/blog/js-array-item-combinations/
const getCombinations = (items) =>
  items.reduce((combos, item) => {
    const newCombos = combos.map((combo) => combo.concat(item))
    combos.push([item], ...newCombos)
    return combos
  }, [])

Getting a single combination

Change .filter() to .find() and fall back to an empty array:

const getCoinCombination = (coins, amount) =>
  getCombinations(coins).find((combo) => sum(combo) === amount) || []

Why this is nice

Straightforward and simple.
No boring for loops.

Why this is naive

First all combinations are generated, then they are looped through again to find matching combinations. This is inefficient, especially when getting only a single combination.
- If coins is a large array (19+ items), getCombinations() gets very slow because the amount of total combinations (before filtering) will be huge.
  
  At some point (32+ coins) the code won't even work anymore because the unfiltered combinations won't fit in a single array.
  
  More details in a separate post: Finding array item combinations for large arrays is complex.
When looping through the combinations to find matching combinations, each combination's sum is calculated. The sums could be calculated earlier to avoid having to:
- loop through them again (in the filter() or find()).
- keep invalid combinations around.

Better solution for getting all combinations

Starting point

Here's the initial solution but without the separate getCombinations function:

const getCoinCombinations = (coins, amount) =>
  coins
    .reduce((combos, coin) => {
      const newCombos = combos.map((combo) => combo.concat(coin))
      combos.push([coin], ...newCombos)
      return combos
    }, [])
    .filter((combo) => sum(combo) === amount)

const sum = (numbers) => numbers.reduce((a, b) => a + b, 0)

Step 1

Each combination in combos is an array of numbers (coins), and each combination's sum is calculated in the filter method.

If the sums were calculated already in the reducer, there would be no need to loop through each combination's coins in the filter method.

This can be done by making each combination an object, like { coins: [1, 2, 1, 5], sum: 9 }:

const getCoinCombinations = (coins, amount) =>
  coins
    .reduce((combos, coin) => {
      const newCombos = combos.map((combo) => ({
        coins: combo.coins.concat(coin),
        sum: combo.sum + coin,
      }))

      combos.push(
        {
          coins: [coin],
          sum: coin,
        },
        ...newCombos
      )

      return combos
    }, [])
    .filter((combo) => combo.sum === amount)
    .map((combo) => combo.coins)

There's a new mapper function at the end, but we'll deal with that soon.

Step 2

Does every combination need to be stored in combos?

Example:

All coins: 1, 2, 1, 5, 5, 10.
Target amount is 12.
Current coin is the second last coin (value 5).
A previous combination has the coins 1, 2, 1 and 5 (→ sum 9).
Question: Does it make sense to create a new combination by adding the current coin (5) to the previous combination's coins?
Answer: The new combination's sum would be 14, which is greater than the target amount (12), so no: creating that combination wouldn't make sense.

Changing combos.map() to combos.forEach() allows conditionally pushing one valid combination at a time to combos:

const getCoinCombinations = (coins, amount) =>
  coins
    .reduce((combos, coin) => {
      combos.forEach((combo) => {
        const newSum = combo.sum + coin
        if (newSum <= amount) {
          combos.push({
            coins: combo.coins.concat(coin),
            sum: newSum,
          })
        }
      })

      if (coin <= amount) {
        combos.push({
          coins: [coin],
          sum: coin,
        })
      }

      return combos
    }, [])
    .filter((combo) => combo.sum === amount)
    .map((combo) => combo.coins)

There's some duplication (the codes inside combos.forEach() and below it look very similar), but we'll deal with that soon.

Step 3

combos contains both incomplete combinations like [2, 5] (sum 7) and complete combinations like [2, 5, 5] (sum 12).

If incomplete and complete combinations were stored separately, the filtering after the reducer would be unnecessary.

This can be done by changing the accumulator array (combos) to an object that contains two arrays ({ complete: [], incomplete: [] }). No need to store sums of the complete combinations (the sums should be equal to amount), so no need for the mapper function after the reducer either:

const getCoinCombinations = (coins, amount) =>
  coins.reduce(
    (combos, coin) => {
      combos.incomplete.forEach((combo) => {
        const newSum = combo.sum + coin

        if (newSum > amount) return

        const newCoins = combo.coins.concat(coin)

        if (newSum === amount) {
          combos.complete.push(newCoins)
        } else {
          combos.incomplete.push({
            coins: newCoins,
            sum: newSum,
          })
        }
      })

      if (coin === amount) {
        combos.complete.push([coin])
      } else if (coin < amount) {
        combos.incomplete.push({
          coins: [coin],
          sum: coin,
        })
      }

      return combos
    },
    { complete: [], incomplete: [] }
  ).complete

Step 4

Final step is to reduce duplication:

const getCoinCombinations = (coins, amount) => {
  return coins.reduce(
    (combos, coin) => {
      combos.incomplete.forEach((combo) => {
        keepComboIfValid(combos, combo.coins, coin, combo.sum + coin)
      })

      keepComboIfValid(combos, [], coin, coin)

      return combos
    },
    { complete: [], incomplete: [] }
  ).complete

  function keepComboIfValid(combos, previousCoins, coin, sum) {
    if (sum > amount) return
    const newCoins = previousCoins.concat(coin)
    if (sum === amount) combos.complete.push(newCoins)
    else combos.incomplete.push({ coins: newCoins, sum })
  }
}

keepComboIfValid mutates the reducer function's accumulator object. But I think that's OK because the mutations are restricted to the getCoinCombinations function, so the mutations are still local. Related blog post: Local mutations are all right.

Potential misstep

It would be tempting to simplify the keepComboIfValid function like this:

// ⛔️ Nope
const getCoinCombinations = (coins, amount) => {
  return coins.reduce(
    (combos, coin) => {
      combos.incomplete.forEach((combo) => {
        keepComboIfValid(combos, {
          coins: combo.coins.concat(coin),
          sum: combo.sum + coin,
        })
      })

      keepComboIfValid(combos, { coins: [coin], sum: coin })

      return combos
    },
    { complete: [], incomplete: [] }
  ).complete

  function keepComboIfValid(combos, combo) {
    if (combo.sum === amount) combos.complete.push(combo.coins)
    else if (combo.sum < amount) combos.incomplete.push(combo)
  }
}

However, this would be less efficient because new combinations are generated and then immediately discarded if they are not valid.

Better solution for getting a single combination

Similar to the previous code, but:

No need to store complete combinations in an array; we want to return the first complete combination immediately when it's found.
A reducer function can't be terminated early, so we need to use for loops instead.

const getCoinCombination = (coins, amount) => {
  const incompleteCombos = []

  for (let coin of coins) {
    if (coin > amount) continue
    if (coin === amount) return [coin]

    for (let i = 0, { length } = incompleteCombos; i < length; i++) {
      const combo = incompleteCombos[i]
      const newSum = combo.sum + coin
      if (newSum > amount) continue
      const newCoins = combo.coins.concat(coin)
      if (newSum === amount) return newCoins
      incompleteCombos.push({ coins: newCoins, sum: newSum })
    }

    incompleteCombos.push({ coins: [coin], sum: coin })
  }

  return []
}

Potential misstep

These wouldn't work for the inner for loop because we are pushing to incompleteCombos inside the loop:

for (let combo of incompleteCombos) {}

for (let i = 0; i < incompleteCombos.length; i++) {}

Both of these would process the newly-pushed combinations, which would be incorrect.

So, the length of incompleteCombos needs to be stored at the beginning of the looping. These two are effectively the same, the second one is just trying to be clever:

for (let i = 0, length = incompleteCombos.length; i < length; i++) {}

for (let i = 0, { length } = incompleteCombos; i < length; i++) {}

JS solutions to the "coin combinations" interview puzzle

Table of contents

Example inputs and outputs

Why though

Initial naive solution

Getting all combinations

Getting a single combination

Why this is nice

Why this is naive

Better solution for getting all combinations

Starting point

Step 1

Step 2

Step 3

Step 4

Potential misstep

Better solution for getting a single combination

Potential misstep