Finding a sequence from given numbers that sum to given value?

Question

Given a set of integers (positive or negative), how can I find a sequence of these numbers that sum to given value?

Example: Given a list of numbers [4,-16, 9, 33], I need the sum 17. I can choose sequence [4, 4, 9](numbers can be reused) or [-16, 33]. I'm trying to find an efficient way to reduce the length of the sequence.

It's like Subset Sum Problem (http://en.wikipedia.org/wiki/Subset_sum) but in my case numbers can be reused.

It's also a little like the Partition problem (Find all possible subsets that sum up to a given number) but in my case there's negative values.

My current greedy algorithm as follows. In each loop I'll try to find a number that minimize the difference between the current sum and target sum.

integers = [-2298478782, 1527301251, 4, 4078748803, 3388759435,
        1583071281, 2214591602, 1528349827, -12, 59460983,
        -939524100, -1, 2315255807]
target_sum = 1997393191

difference = target_sum
chain = list()
while difference != 0:
    min_abs_difference = abs(difference)
    next_int = 0
    found = False
    for i in integers:
        new_abs_diff = abs(i+difference)
        if new_abs_diff < min_abs_difference:
            found = True
            next_int = i
            min_abs_difference = new_abs_diff
    if not found:
        print(difference)
        print(chain)
        print("Cannot find an integer that makes difference smaller")
        break
    difference += next_int
    chain.append(next_int)
print(chain)

Answer 1

There most likely isn't a fast algorithm that gives an optimal solution. The subset-sum problem is NP-complete and that problem is easier than your problem (because you allow reuse of numbers).

Given that the problem is NP-complete I think you should focus on improving your current algorithm or rewrite it in a faster language such as C. You can then call your C code from Python.

Answer 2

Since it is obviously at least NP complete problem you can think of formulating it as a Mixed Integer Linear Programming Problem.

Minimize summation( Xi ) // Xi = number of times the array element Ai is used.
Subject To
     summation( Ai*Xi ) = S.
     Xi >= 0 { Xi are all integers }

You can solve it using any solver.