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.