How to find the shortest square sum of a number

Question

Find and output the given number's shortest square sum.

Example: 12 = 2^2 + 2^2 + 2^2 (not 3^2 + 1^2 + 1^2 + 1^2)

Output: {2 2 2}

Answer 1

This is min-coin-change problem, where the coins are [1,4,9,...,(ceil(sqrt(n)))^2].

It can be solved using Dynamic Programming (DP) by following the recurrence formula:

D(i,0) = 0
D(i,x) = infinity    x<0
D(0,x) = infinity    x>0
D(i,x) = min { D(i,x-i^2) + 1, D(i-1,x) }

When building your matrix (assuming bottom-up DP), the element denoted in the matrix in D(ceil(sqrt(n)),n) is the minimal number of "coins" (squared numbers) needed to build your input number.

Getting the actual elements is done by tracking back your choices in the matrix after it is built, and at each point checking if you added a summand or not.
This is explained in more details for similar problems in this thread and this thread.

Answer 2

Here is a visual basic solution to the problem. An edit would need to be done to cache intermediate answers so that the algorithm would be significantly faster. Currently ... only a value of about 40 to 50 is quickly computed. This is fully working and tested. It only returns the shortest answer and one where the higher value are to the left of other values.

Private Function ShortestSquareSum(x As Integer) As Integer()()
    If x < 0 Then
        Throw New ArgumentException("Parameter cannot be negative.", "x")
    ElseIf x = 0 Then
        Return New Integer()() {New Integer() {}}
    Else
        Dim answers As New List(Of Integer())
        Dim shortest As Integer? = Nothing
        For y As Integer = Math.Floor(Math.Sqrt(x)) To 1 Step -1
            Dim remaining As Integer = x - y * y
            Dim tempAnswers As Integer()() = ShortestSquareSum(x - y * y)
            For Each answer As Integer() In tempAnswers
                Dim currentAnswer As New List(Of Integer)
                currentAnswer.Add(y)
                currentAnswer.AddRange(answer)
                If Not shortest.HasValue OrElse currentAnswer.Count < shortest Then
                    shortest = currentAnswer.Count
                    answers.Clear()
                    answers.Add(currentAnswer.ToArray())
                ElseIf currentAnswer.Count = shortest AndAlso (answer.Count = 0 OrElse y > answer(0)) Then
                    answers.Add(currentAnswer.ToArray())
                End If
            Next
        Next
        Return answers.ToArray()
    End If
End Function

Answer 3

public static void shortest_square(int n)
{
    int i=2;
    List<Integer> list= new ArrayList<Integer>();
    while(i<=n) || n!=0)
    {
     if(n%(i*i)==0)
     {
      n=n-(i*i);
      list.add(i);
     }
     else
     {
      i++;
     }

    }
    System.out.println(list);
}