Of course, Dynamic Programming solution is better.
But for your info there is a theorem of Lagrange.
Quote from Wikipedia
"Lagrange's four-square theorem states that any natural number can be represented as the sum of four integer squares"
http://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem Example,
3 = 1^2 + 1^2 + 1^2 + 0^2
31 = 5^2 + 2^2 + 1^2 + 1^2
310 = 17^2 + 4^2 + 2^2 + 1^2.
Here is my C# code:
using System;
class Program
{
static void Main()
{
int n = int.Parse(Console.ReadLine());
for (int i1 = 0; i1 <= (int)Math.Sqrt(n); i1++)
for (int i2 = 0; i2 <= (int)Math.Sqrt(n); i2++)
for (int i3 = 0; i3 <= (int)Math.Sqrt(n); i3++)
for (int i4 = 0; i4 <= (int)Math.Sqrt(n); i4++)
if (i1 * i1 + i2 * i2 + i3 * i3 + i4 * i4 == n)
{ Console.WriteLine(Math.Sign(i1)+Math.Sign(i2)+Math.Sign(i3)+Math.Sign(i4)); return; }
}
}
