How can you determine if a number is sum of some squared numbers?

Question

I have an algorithmic question: How can we determine if a number equals the sum of some different squared numbers? For example : 50 = 4*4 + 5*5 + 3*3

And, If it is true, How can I find the number of states that we can write as a sum of several different squares?

25 = 5^2 + 0 or 3^2 + 4^2 and It has 2 states.

I am ok with 2 numbers and I know that We can solve it with Recursion.

Here is my code in java for 2 numbers :

import java.util.Scanner;

public class SemiCharismatic {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int number = input.nextInt();
        input.close();
        if (isSquare(number) == true) {
            System.out.print("YES");
            System.exit(0);
        } else {
            for (int i = 1; i < number; i++) {
                int j = number - i;
                if (isSquare(i) == true && isSquare(j) == true) {
                    System.out.print("YES");
                    System.exit(0);
                }
            }
            System.out.print("NO");
        }
    }

    static boolean isSquare(int number) {
        boolean result = false;
        if (Math.sqrt(number) - Math.floor(Math.sqrt(number)) == 0) {
            result = true;
        }
        return result;
    }
}

Answer 1

This can be looked at as the coin exchange problem (see here).

One method of solving the coin exchange problem is recursive, as the other answer suggested:

def is_sum_squared_rec(number, candidates=None, idx=None):
    if candidates is None:
        candidates = np.arange(1, int(np.floor(np.sqrt(number)))+1) ** 2
        idx = len(candidates) - 1
    if (number > 0 and idx == -1) or number < 0:
        return False
    if number == 0:
        return True
    return is_sum_squared_rec(number, candidates, idx-1) or is_sum_squared_rec(number-candidates[idx], candidates, idx-1)

But another non recursive method of implementing the coin exchange problem in this case will be as follows:

def is_sum_squared(number):
    counts = [1] + [0] * number
    candidates = np.arange(1, int(np.floor(np.sqrt(number))) + 1) ** 2
    for candidate in candidates:
        for jj in range(number, candidate-1, -1):
            counts[jj] += counts[jj - candidate]
    return counts[number] > 0

This method avoids performing redundant computations and should be faster than the recursive method.

The non-recursive method could be improved further since we do not want the whole count, just if it can be broken into a sum of candidates. therefore we can introduce an early stop condition:

def is_sum_squared_early_stop(number):
    counts = [1] + [0] * number
    candidates = np.arange(1, int(np.floor(np.sqrt(number))) + 1) ** 2
    for candidate in candidates:
        for jj in range(number, candidate-1, -1):
            counts[jj] += counts[jj - candidate]
            if counts[number] > 0:
                return True
    return counts[number] > 0

The runtime of the non-recursive algorithm is O(n*sqrt(n)) and the scape requirements is O(n).

Timing

for number = 400, timing resulted in the following:

%timeit is_sum_squared_rec(400)
1.88 ms ± 177 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit is_sum_squared(400)
1.05 ms ± 76.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit is_sum_squared_early_stop(400)
796 µs ± 127 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Almost a factor of 3 improvement. When checking with number=3000 we get:

%timeit is_sum_squared_rec(3000)
1.81 s ± 152 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit is_sum_squared(3000)
24.5 ms ± 581 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit is_sum_squared_early_stop(3000)
14.3 ms ± 556 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

And we have more than 2 orders of magnitude difference

Answer 2

This problem is a variant of Subset sum problem.

Here you'll have to create a set of your own (which is explained below) and your number is the target sum for the problem.

To create a set, form an array of numbers [square of numbers from {1 to sqrt(n)}]

So your array will look like: [1,4,9... sqrt(n)^2]

To explain why sqrt(n): The square of any number greater than sqrt(n) will also be greater than n. Hence adding more to it will not lead to a solution.

Then apply the subset-set algorithm, as explained here

isSubsetSum(set, n, sum) 
= isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0