JS solutions to the "coin combinations" interview puzzle
Published on 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."
Table of contents
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
 Find all possible coin combinations.
 I have a separate post for that: Finding all possible combinations of array items 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/jsarrayitemcombinations/
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()
orfind()
).  keep invalid combinations around.
 loop through them again (in the
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 newlypushed 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++) {}