not homework... something i find an interesting problem

[Trip Technician]

Thank you Dave. This does it but slowly. takes every subset of the
list a of squares, and then gets a 'partition' that will work, many
are very inefficient (with lots of 1s).

any hints about how to speed up ?


def subset(x):
    for z in range(1,2**len(x)):
        q=bin(z)
        subs=[]
        for dig in range(len(q)):
            if q[dig]=='1':
                subs.append(x[dig])
        yield subs

def bin(x):
  q=""
  while x>=1:
    q+=str(x%2)
    x//=2
  return q



def squ(z,b):
    if z==0:
        return 0
    for x in b:
        if z>=x:
            return x,squ(z-x,b)


def flatten(lst):
    for elem in lst:
        if type(elem) in (tuple, list):
            for i in flatten(elem):
                yield i
        else:
            yield elem



sizelim=150

a=[x**2 for x in range(int(sizelim**0.5),1,-1)]

q,r=[],[]

for aa in range(sizelim):
    r.append([])


for xx in range(1,sizelim):
    for z in subset(a):
        q=[]
        z.append(1)
        for rr in flatten(squ(xx,z)):
            if rr !=0:
                q.append(rr)
        item=[len(q),q]
        if item not in r[xx]:
            r[xx].append(item)
            r[xx].sort()

for eee in r:
    if eee:
            print r.index(eee),eee[0:3]