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 n2.

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.