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)