Write a recursive function named printSquares that accepts an integer n as a parameter and uses backtracking to find all ways to express that integer n as a sum of squares of unique positive integers.
For example, the call of printSquares(200); should produce the following output:
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
Some numbers (such as 128 or 0) cannot be represented as a sum of squares, in which case your function 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 1^2 together until you got to whatever total amount n you are working with.
If the value of n passed is negative, your function should throw an integer exception.
Constraints:
You may use a loop in your solution if you like, but the overall algorithm must use recursion and backtracking.
You may define helper functions if you like.
To help you solve this problem, assume there already exists a function named display that accepts any collection of integers (such as a vector, set, stack, queue, etc.) and prints the collection's elements in order in the format below.
For example, if a vector v stores the elements {1, 4, 8, 11}, the call of display(v); would produce the following output:
1^2 + 4^2 + 8^2 + 11^2
