Find smallest number of squares that sum to a number
Not an review, but an extended comment:

I don't know how this solution can be optimized. The expected solution is radically different, and is based on a couple of theorems from number theory.

You should check whether the number is


A perfect square (the answer is obviously 1), or
is a sum of 2 squares (the answer is obviously 2), or
not a Legendre's number, that is \$n = 4^a(8b + 7)\$ (the answer is 3)


Otherwise, the answer is 4.