You have the memoization keyed by the value to be attained, but this does not take into account the value of index, which actually puts restrictions on which powers you can use to attain that value. That means that if (in the extreme case) index is 0, you can only reduce what is left with one square (1²), which rarely is the optimal way to form that number. So in a first instance memo.set() will register a non-optimal number of squares, which later will get updated by other recursive calls which are pending in the recursion tree.

If you add some conditional debugging code, you’ll see that map.set is called for the same value of left multiple times, and with differing values. This is not good, because that means the if (memo.has(left)) block will execute for cases where that value is not guaranteed to be optimal (yet).

You could solve this by incorporating the index in your memoization key. This increases the space used for memoization, but it will work. I assume you can work this out.

But according to Lagrange’s four square theorem every natural number can be written as the sum of at most four squares, so the returned value should never be 5 or more. You can shortcut the recursion when you get passed that number of terms. This reduces the benefit of using memoization.

Finally, there is a mistake in fillSquares: it should add n itself also when it is a perfect square, otherwise you’ll not find solutions that should return 1.

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top