from collections import defaultdict
 
data = [1, 2, 4]
target_sum = 10
 
# T[x, i] is True if 'x' can be solved
# by a linear combination of data[:i+1]
T = defaultdict(bool)           # all values are False by default
T[0, 0] = True                # base case
 
 
for i, x in enumerate(data):    # i is index, x is data[i]
    for s in range(target_sum + 1): #set the range of one higher than sum to include sum itself
        for c in range(s // x + 1):  
            if T[s - c * x, i]:
                T[s, i+1] = True
 
coeff = [0]*len(data)
 
def RecursivelyListAllThatWork(k, sum_): # Using last k variables, make sum
    # /* Base case: If we've assigned all the variables correctly, list this
    # * solution.
    # */
    if k == 0:
        # print what we have so far
        terms = list(zip(coeff, data))
        print("%s = %s" % (' + '.join("%2s*%s" % t for t in terms), sum(t[0]*t[1] for t in terms)))
        return
    x_k = data[k-1]
    # /* Recursive step: Try all coefficients, but only if they work. */
    for c in range(sum_ // x_k + 1):
       if T[sum_ - c * x_k, k - 1]:
           # mark the coefficient of x_k to be c
           coeff[k-1] = c
           RecursivelyListAllThatWork(k - 1, sum_ - c * x_k)
           # unmark the coefficient of x_k
           coeff[k-1] = 0
 
RecursivelyListAllThatWork(len(data), target_sum)

ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVmYXVsdGRpY3QKCmRhdGEgPSBbMSwgMiwgNF0KdGFyZ2V0X3N1bSA9IDEwCgojIFRbeCwgaV0gaXMgVHJ1ZSBpZiAneCcgY2FuIGJlIHNvbHZlZAojIGJ5IGEgbGluZWFyIGNvbWJpbmF0aW9uIG9mIGRhdGFbOmkrMV0KVCA9IGRlZmF1bHRkaWN0KGJvb2wpICAgICAgICAgICAjIGFsbCB2YWx1ZXMgYXJlIEZhbHNlIGJ5IGRlZmF1bHQKVFswLCAwXSA9IFRydWUgICAgICAgICAgICAgICAgIyBiYXNlIGNhc2UKCgpmb3IgaSwgeCBpbiBlbnVtZXJhdGUoZGF0YSk6ICAgICMgaSBpcyBpbmRleCwgeCBpcyBkYXRhW2ldCiAgICBmb3IgcyBpbiByYW5nZSh0YXJnZXRfc3VtICsgMSk6ICNzZXQgdGhlIHJhbmdlIG9mIG9uZSBoaWdoZXIgdGhhbiBzdW0gdG8gaW5jbHVkZSBzdW0gaXRzZWxmCiAgICAgICAgZm9yIGMgaW4gcmFuZ2UocyAvLyB4ICsgMSk6ICAKICAgICAgICAgICAgaWYgVFtzIC0gYyAqIHgsIGldOgogICAgICAgICAgICAgICAgVFtzLCBpKzFdID0gVHJ1ZQoKY29lZmYgPSBbMF0qbGVuKGRhdGEpCgpkZWYgUmVjdXJzaXZlbHlMaXN0QWxsVGhhdFdvcmsoaywgc3VtXyk6ICMgVXNpbmcgbGFzdCBrIHZhcmlhYmxlcywgbWFrZSBzdW0KICAgICMgLyogQmFzZSBjYXNlOiBJZiB3ZSd2ZSBhc3NpZ25lZCBhbGwgdGhlIHZhcmlhYmxlcyBjb3JyZWN0bHksIGxpc3QgdGhpcwogICAgIyAqIHNvbHV0aW9uLgogICAgIyAqLwogICAgaWYgayA9PSAwOgogICAgICAgICMgcHJpbnQgd2hhdCB3ZSBoYXZlIHNvIGZhcgogICAgICAgIHRlcm1zID0gbGlzdCh6aXAoY29lZmYsIGRhdGEpKQogICAgICAgIHByaW50KCIlcyA9ICVzIiAlICgnICsgJy5qb2luKCIlMnMqJXMiICUgdCBmb3IgdCBpbiB0ZXJtcyksIHN1bSh0WzBdKnRbMV0gZm9yIHQgaW4gdGVybXMpKSkKICAgICAgICByZXR1cm4KICAgIHhfayA9IGRhdGFbay0xXQogICAgIyAvKiBSZWN1cnNpdmUgc3RlcDogVHJ5IGFsbCBjb2VmZmljaWVudHMsIGJ1dCBvbmx5IGlmIHRoZXkgd29yay4gKi8KICAgIGZvciBjIGluIHJhbmdlKHN1bV8gLy8geF9rICsgMSk6CiAgICAgICBpZiBUW3N1bV8gLSBjICogeF9rLCBrIC0gMV06CiAgICAgICAgICAgIyBtYXJrIHRoZSBjb2VmZmljaWVudCBvZiB4X2sgdG8gYmUgYwogICAgICAgICAgIGNvZWZmW2stMV0gPSBjCiAgICAgICAgICAgUmVjdXJzaXZlbHlMaXN0QWxsVGhhdFdvcmsoayAtIDEsIHN1bV8gLSBjICogeF9rKQogICAgICAgICAgICMgdW5tYXJrIHRoZSBjb2VmZmljaWVudCBvZiB4X2sKICAgICAgICAgICBjb2VmZltrLTFdID0gMAoKUmVjdXJzaXZlbHlMaXN0QWxsVGhhdFdvcmsobGVuKGRhdGEpLCB0YXJnZXRfc3VtKQ==