###### Books / Introduction to Recursion and Backtracking / Chapter 11

# Backtracking Example - The Sum of Four Squares

LaGrange’s 4-squares theorem states that any natural number can be written as the sum of four squares (including 0 if need be.) Suppose we wanted an algorithm that, given any natural number, could find four squares whose sum equals the number. Backtracking can do this. The idea is to pick a square less than the number, subtract it, and then find three numbers that add up to the difference. If we succeed, then we found the four numbers. If we do not, then we back up to the first number we picked and try a different first number. We can proceed by picking the smallest first number first, or by picking the largest first number first. Either way we can proceed methodically. The algorithm below picks the smallest number first.

```
int tryout_solution(int number, int num_squares) {
int i;
if (number == 0) {
// If number == 0 it can be written as the sum of however many 0's we
// need so we have succeeded .
return true;
}
// assert: number > 0
if (num_squares == 0)
// If we reach here, since number > 0 and we have used up our quota of
// four squares, we could not find 4 square s whose sum is number
return false;
// try to find a number i such that i * i is less than number
// if we do , then subtract i * i from the number and recursively
// do the same thing for number−i * i with one less square than before.
// if one particular i fails, we try the next i . This is the backtracking part
for (i = 1; i * i <= number; i++) {
int square = i * i;
if (tryout_solution(number− square, num_squares− 1)) {
printf(" %d", square);
if (num_squares < 4)
printf(" + ");
return true;
}
}
return false;
}
```

The above function would be called with an initial value of *4* for the second parameter, `num_squares`

, as in:

```
if (tryout_solution(value, 4))
printf(" = %d\n", value);
```

The function attempts to find `num_squares`

squares that sum to `number`

. If number is zero, it is trivial to
satisfy so it returns `true`

. Since each recursive call diminishes `num_squares`

, it is possible that it is zero.
If `number`

is not zero but `num_squares`

is zero, it means that it has run out of chances - it has used four
squares but their sum is not the original number, so it returns false. Otherwise there is still hope - for
each square less than `number`

, it calls `tryout_solution(number-square, num_squares-1)`

, hoping that
one of those squares will result in `tryout_solution()`

returning `true`

. If it does, it means that it found
the remaining squares and that `square`

is one of the squares that add up to `number`

. It prints the value
of `square`

(with a ‘+’ after if need be), and returns to the calling function. If the main program is named
`find_lagrange_squares`

, the output could look like:

```
$ find_lagrange_squares 2000
1764 + 196 + 36 + 4 = 2000
```