# Project Euler - Problem 31: Coin sums

Tell us what’s happening:
Ok, I am stuck on the stage ‘what should I google for this one’.
My first idea is just generate power set of all these coins, but I don’t even wanna go there, because it’s exponential complexity stuff.

I feel like I am missing some basic algorithm knowledge to come up with decent approach. So the hints in terms of where to start research are appreciated.

``````  **Your code so far**
``````
``````function coinSums(n) {
const coins = [1, 2, 5, 10, 20, 50, 100, 200];
return n;
}

coinSums(200);
``````
``````  **Your browser information:**
``````

User Agent is: `Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/104.0.0.0 Safari/537.36`

Challenge: Project Euler - Problem 31: Coin sums

Yes, I definitely see how memoization can be used here, so great thanks for that direction.

I’ve run into another issue: even when I wrote manually test cases for all possible `n` from 1 to 10, I still wasn’t able to come up with patterns which would allow me to build the algorithm.

But now I found out that this challenge is about some typical combinatorics problem, so I am diving into some math right now.

I moved further and have some code.

Now the problem I am facing is this:

for `n===3`
expected behaviour is returning `2`
because combos for this case are:

• 111, 21

However, my solution is returning 3, because it is considering `21` and `12` two different combos and spitting amount of combos for

• 111, 21, 12

If I will start building some arrays or strings dynamically I can sort them and remove duplicates. But I am afraid this will increase complexity too much. One way to find out tho.

The code for now:

``````function coinSums(n, memo = {}) {
// console.log(n, memo); //>>> testing purposes only
//  memoizing
if (n in memo) {return memo[n];}
const coins = [1, 2, 5, 10, 20, 50, 100, 200];
// base cases
if (n === 0) {return 1;}
// if (n < 0) {return 0;} //>>> not needed it's better to quit the loop early than increase stack with this
// recursive step
let combos = 0;
for (let coin of coins) {
if (coin > n) {break;} // for n === 8 steps for coins 10 and higher not needed
combos += coinSums(n - coin, memo);
}
memo[n] = combos
return memo[n];
}

for (let i = 1; i <=10; i++) {
console.log('CASE ', i);
console.log('RESULT ', coinSums(i));
console.log('--------------');
}
``````

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.