# Acquiring an increasing sequence of numbers

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.

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.