I know how to check if the number can be represented as the sum of two squares with a brute-force approach.

def sumSquare( n) :
    i = 1
    while i * i <= n :
        j = 1
        while(j * j <= n) :
            if (i * i   j * j == n) :
                print(i, "^2   ", j , "^2" )
                return True
            j = j   1
        i = i   1

    return False

But how to do it for n distinct positive integers. So the question would be:

Function which checks if the number can be written as sum of 'n' different squares

I have some examples.

For e.g.

1. is_sum_of_squares(18, 2) would be false because 18 can be written as the sum of two squares (3^2 3^2) but they are not distinct.
2. (38,3) would be true because 5^2 3^2 2^2 = 38 and 5!=3!=2.

I can't extend the if condition for more values. I think it could be done with recursion, but I have problems with it.

I found this function very useful since it finds the number of squares the number can be split into.

def findMinSquares(n):
    T = [0] * (n   1)
    for i in range(n   1):
        T[i] = i
        j = 1
        while j * j <= i:
            T[i] = min(T[i], 1   T[i - j * j])
            j  = 1

    return T[n]

But again I can't do it with recursion. Sadly I can't wrap my head around it. We started learning it a few weeks ago (I am in high school) and it is so different from the iterative approach.

CodePudding user response：

Recursive approach:

def is_sum_of_squares(x, n, used=None):
    x_sqrt = int(x**0.5)
    if n == 1:
        if x_sqrt**2 == x:
            return used.union([x_sqrt])
        return None
    used = used or set()
    for i in set(range(max(used, default=0) 1, int((x/n)**0.5))):
        squares = is_sum_of_squares(x-i**2, n-1, used.union([i]))
        if squares:
            return squares
    return None