logo CodeStepByStep logo

printSquares

Language/Type: C++ recursion backtracking
Author: Marty Stepp (on 2016/06/16)

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

Type your C++ solution code here:


This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.


Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.