sum_squares.py

import math

cache = {}
low = 1


def f(n, squares):
    global low
    if n in squares:
        return [n]
    elif n in cache:
        return cache[n]
    else:
        # not in cache
        result = []

        # build cache, DP
        for i in range(low, n/2+1):
            if n not in cache:
                cache[n] = f(n-i, squares) + f(i, squares)
                low = n

        return cache[n]

def sum_squares(N):
    """
    Give N, find out { n | sigma n^2 = N }
    """
    squares = map(lambda x: x**2, range(1, int(math.floor(N ** 0.5)+1)))
    return f(N, squares)

i = 100000
ans = sum_squares(i)
print 'sum: %s' % sum(ans), 'sum len: %s' %len(ans), 'cache size: %s' % len(cache)