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.

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.

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