**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

**Link to the challenge:**

This is another dynamic programming problem.

1 Like

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:

However, my solution is returning 3, because it is considering `21`

and `12`

two different combos and spitting amount of combos for

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('--------------');
}
```