Write a recursive method called printSquares to find all ways to express an integer as a sum of squares of unique positive integers. For example, the call printSquares(200); should produce the following output:

Some numbers (such as 128 or 0) cannot be represented as a sum of squares, in which case your method should produce no output. Keep in mind that the sum has to be formed with unique integers. Otherwise you could always find a solution by adding 12 together until you got to whatever number you are working with.

As with any backtracking problem, this one amounts to a set of choices, one for each integer whose square might or might not be part of your sum. You may generate the choices by doing a for loop over an appropriate range of numbers. Note that the maximum possible integer that can be part of a sum of squares for an integer n is the square root of n.

Transcribed Image Text:

1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 8^2 + 9^2 1^2 + 2^2 + 3^2 + 4^2 + 7^2 + 11^2 1^2 + 2^2 + 5^2 + 7^2 + 11^2 1^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 + 8^2 1^2 + 3^2 + 4^2 + 5^2 + 7^2 + 10^2 2^2 + 4^2 + 6^2 + 12^2 2^2 + 14^2 3^2 + 5^2 + 6^2 + 7^2 +9^2 6^2 + 8^2 + 10^2