Find the smallest number of perfect squares that sum to a target

Question

Given a positive integer n, find the smallest number of perfect squares (for example, 1, 4, 9, 16, ...) that sum to n.

sums = {0:0, 1:1}
def numSquares(n: int) -> int:
    if n in sums:
        return sums[n]
    else:
        s = 2**31
        squares = [i**2 for i in range(1, int(n**(1/2)) + 1)]
        while len(squares) and squares[-1] > n:
            squares.pop()
        for i in squares:
            s = min(s, numSquares(n - i) + 1)
        sums[n] = s
        return s

I'm also having a bit of trouble calculating the time complexity (using Big O notation) due to the recursion.

I understand that it's at least \$O(\sqrt n)\$ due to the loop but I'm unsure of how to factor in the recursive call.

Thank you very much!

Answer 1

Caching

You are using sums as a cache for your dynamic programming. Python comes with built-in caching (functools.lru_cache), so you don't need to implement your own. Using it will avoid polluting the global namespace.

Integer Square-Root

With Python3.8 comes a built-in math.isqrt, rendering the idiom int(n**(1/2)) obsolete.

Unnecessary filtering

    squares = [i**2 for i in range(1, isqrt(n) + 1)]
    while len(squares) and squares[-1] > n:
        squares.pop()

Here, you are generating all the squares up to (and including if it is a perfect square) n. Then, you check if the last item is larger than n. It is impossible for it to be, so squares.pop() will never be executed, making the entire while loop redundant code which can be deleted.

Unnecessary (and suspicious) minimum

    s = 2**31
    for i in squares:
        s = min(s, numSquares(n - i) + 1)

Here, 2**31 is used as a value larger than any possible value, so you can compute the minimum in the for loop. But is it really larger than any possible value??? I can think of larger values, but perhaps it comes from the challenge text.

Still, Python provides a better way: the min(...) function and list comprehension:

    s = min(numSquares(n - i) + 1 for i in squares)

This loops through all squares, and evaluates numSquares(n - i) + 1 for each one, and selects the minimum value. No magic "value larger than any possible value" value is required.

Still, it can be made even more efficient. If there are 10,000 squares, we add one to each result, and take the minimum. That's 10,000 plus one operations. If we compute the minimum value, and add one to that, we've saved 9,999 additions.

    s = min(numSquares(n - i) for i in squares) + 1

Unnecessary list creation

The code would now read:

    squares = [i**2 for i in range(1, isqrt(n) + 1)]
    s = min(numSquares(n - i) for i in squares) + 1

We create a list of squares and then immediately loop through that list exactly once, and never use it again. Creating the list is an unnecessary step, that consumes memory and wastes time. Just compute the squares on the fly!

    s = min(numSquares(n - i ** 2) for i in range(1, isqrt(n) + 1)) + 1

PEP-8

Functions and variables should be in snake_case, not mixedCase. Your function should be named num_squares.

There should be a space around binary operators like ** and /.

Variable names like s are meaningless. Variable names should be descriptive. s is the minimum count of the terms summing to n; min_terms would be more descriptive.

Updated Code

from functools import lru_cache
from math import isqrt

@lru_cache(maxsize=None)
def num_squares(n: int) -> int:

    root_n = isqrt(n)
    if root_n ** 2 == n:
        return 1

    return min(num_squares(n - i ** 2) for i in range(1, root_n + 1)) + 1

Further improvements

Consider 10001. It is not a perfect square. So you start subtracting squares off it, beginning with \$1^2\$ and discover \$10001 - 1^2 = 100^2\$, for min_terms of 2. You should stop searching; there will be no better answer. But instead, you will continue with \$10001 - 2^2\$, and figure out the num_squares() of that, and then try \$10001 - 3^2\$ and so on. This is all busy work.

Determining how to prune the search tree left as exercise to student.