# JS solutions to the "coin combinations" interview puzzle

Published on

"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."

## Example inputs and outputs

``````let coins = [1, 2, 1, 5, 5, 10]
let amount = 12
getCoinCombinations(coins, amount)
//=> [[1, 1, 5, 5],  [1, 1, 10],  [2, 5, 5],  [2, 10]]

coins = [2, 5, 5, 5]
amount = 13
getCoinCombinations(coins, amount)
//=> []
``````

A slight variation to the puzzle is to return only one valid combination:

``````let coins = [1, 2, 1, 5, 5, 10]
let amount = 12
getCoinCombination(coins, amount)
// Any of the following is valid:
//=> [1, 1, 5, 5]
//=> [1, 1, 10]
//=> [2, 5, 5]
//=> [2, 10]
``````

Let's solve both puzzles.

## Why though

It was fun to solve this!

## Initial naive solution

1. Find all possible coin combinations.
2. 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++) {}
``````