Descomponer el número en la menor cantidad de cuadrados

Tarea: El usuario introduce un número no mayor a 10 000 000, el programa debe descomponer el número en la suma de cuadrados de manera que estos cuadrados sean la menor cantidad posible.

Ejemplo: 34 = 25+9

35 = 25+9+1

32+16

39 = 25+9+4+1

Honestamente, sé Python en 6+, pero no pensaré el algoritmo en sí, ayuda al menos con eso.