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 &lt; 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.
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.