Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Any combination of perfect square numbers with or without repetitions may yield the sum

We enumerate all and find the ones with the least number

Note the greedy approach does not work:  For example to get 12, we cannot say 9 + 1 + 1 + 1

void SquareSums(ref List<int> perfectsquares, ref List<int>candidate, int n, int start, int level)
{

for (int I = start; I < n; I++)

{

for (int j = 1; j <= n/perfectsquares[I]; j++)

{

for (int k = 0; k < j; k ++){
       candidate[level+k] = perfectsquares[i];
}

if (candidate.sum() == n) Console.WriteLine("{0} with {1} elements", candidate.ToString(),
candidate.Count());

if (candidate.sum() < n)

      SquareSums( ref perfectsquares, ref candidate, n, start+1, level+j);

for(int k = 0; k <j; k++){
      candidate[level+k] = 0;
}
}


}

}