title: Finding a sequence from given numbers that sum to given value?
body: <p>Given a set of integers (positive or negative), how can I find a sequence of these numbers that sum to given value?</p>
  
  <p>Example: Given a list of numbers <code>[4,-16, 9, 33]</code>, I need the sum <code>17</code>. I can choose sequence <code>[4, 4, 9]</code>(numbers can be reused) or <code>[-16, 33]</code>. I'm trying to find an efficient way to reduce the length of the sequence.</p>
  
  <p>It's like <code>Subset Sum Problem</code> (<a href="http://en.wikipedia.org/wiki/Subset_sum" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Subset_sum</a>) but in my case numbers can be reused.</p>
  
  <p>It's also a little like the Partition problem (<a href="https://stackoverflow.com/questions/8330371/find-all-possible-subsets-that-sum-up-to-a-given-number">Find all possible subsets that sum up to a given number</a>) but in my case there's negative values.</p>
  
  <p>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.</p>
  
  <pre><code>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 &lt; 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)
  </code></pre>