# list all solutions of non-negative x where
# a dot-product x = ba
# *a must be in descending order
def frobenius_solve(a, b):
n = len(a)
h = {}
def f(i, c):
if c == 0:
return [[]]
if i == len(a):
return []
k = (i, c)
if k not in h:
d = a[i]
r = []
for j in range(c // d + 1):
for x in f(i+1, c - d*j):
y = [j]
y.extend(x)
r.append(y)
h[k] = r
return h[k]
r = f(0, b)
for x in r:
while len(x) < n:
x.append(0)
return r
A = [12, 16, 20, 27]
B = 123
for x in frobenius_solve(A[::-1], B):
print(' '.join(map(str, x[::-1])))
IyBsaXN0IGFsbCBzb2x1dGlvbnMgb2Ygbm9uLW5lZ2F0aXZlIHggd2hlcmUKIyBhIGRvdC1wcm9kdWN0IHggPSBiYQojICphIG11c3QgYmUgaW4gZGVzY2VuZGluZyBvcmRlcgpkZWYgZnJvYmVuaXVzX3NvbHZlKGEsIGIpOgogICAgbiA9IGxlbihhKQogICAgaCA9IHt9CiAgICBkZWYgZihpLCBjKToKICAgICAgICBpZiBjID09IDA6CiAgICAgICAgICAgIHJldHVybiBbW11dCiAgICAgICAgaWYgaSA9PSBsZW4oYSk6CiAgICAgICAgICAgIHJldHVybiBbXQogICAgICAgIGsgPSAoaSwgYykKICAgICAgICBpZiBrIG5vdCBpbiBoOgogICAgICAgICAgICBkID0gYVtpXQogICAgICAgICAgICByID0gW10KICAgICAgICAgICAgZm9yIGogaW4gcmFuZ2UoYyAvLyBkICsgMSk6CiAgICAgICAgICAgICAgICBmb3IgeCBpbiBmKGkrMSwgYyAtIGQqaik6CiAgICAgICAgICAgICAgICAgICAgeSA9IFtqXQogICAgICAgICAgICAgICAgICAgIHkuZXh0ZW5kKHgpCiAgICAgICAgICAgICAgICAgICAgci5hcHBlbmQoeSkKICAgICAgICAgICAgaFtrXSA9IHIKICAgICAgICByZXR1cm4gaFtrXQogICAgciA9IGYoMCwgYikKICAgIGZvciB4IGluIHI6CiAgICAgICAgd2hpbGUgbGVuKHgpIDwgbjoKICAgICAgICAgICAgeC5hcHBlbmQoMCkKICAgIHJldHVybiByCgpBID0gWzEyLCAxNiwgMjAsIDI3XQpCID0gMTIzCmZvciB4IGluIGZyb2Jlbml1c19zb2x2ZShBWzo6LTFdLCBCKToKCXByaW50KCcgJy5qb2luKG1hcChzdHIsIHhbOjotMV0pKSk=