Acquiring an increasing sequence of numbers

Question

I'm trying to solve this question:

Given a positive integral number n, return a strictly increasing sequence (list/array/string depending on the language) of numbers, so that the sum of the squares is equal to n².

If there are multiple solutions (and there will be), return the result with the largest possible values:

Basically, a squared number deconstructed into smaller squares. However, my code only works for smalls numbers efficiently (20 being roughly the max) and is exponentially slower onwards. How can I develop this code?

I tried optimising it by reducing the memory usage by setting comb to take out any bits of irrelevant data.

import itertools as it
from math import sqrt


def decompose(n):
    squares = [i ** 2 for i in range(1, n) if (i ** 2)/2 < n ** 2]
    comb = [list(i) for i in (reduce(lambda acc, x: acc + list(it.combinations(squares, x)),
                                     range(1, len(squares) + 1), [])) if sum(i) == n ** 2]
    print [int(sqrt(i)) for i in max(comb)]


decompose(20)

I am a beginner with Python so any optimisation tips will be greatly appreciated.

Answer 1

I would suggest focusing on the nature of the answer. The requirement is to return the highest possible values, which also means the shortest sequence.

So I would suggest you start at n-1 and work your way down, checking increasingly long sequences until one sums to greater than n**2, in which case you can restart at n-2, etc.