World's most popular travel blog for travel bloggers.

Sum to a certain value of a group of integers

, ,
Problem Detail:

Take a group filled with an arbitrary number of random integers. Is there any way of finding out whether it is possible for the sum of the integers can equal a certain number, with the condition that any of the integers can (but do not have to) be multiplied by 0 or -1?

The only possible solution I could think of was to have the algorithm test all possible sums with each integer multiplied by 0 or -1, but this seems to be extremely inefficient, especially with larger groups of integers.

Example:

2 40 6 7 6 2 can sum to 30 ([0*2] [40] [-1*6] [0*7] [-1*6] [2])

This is basically the subset sum problem, which is well-studied. In particular, there is no efficient algorithm for solving all instances of this problem.

There's a small twist in your version of the problem: you allow multiplying numbers by -1. However, your problem can still be reduced to the subset problem, by simply appending the negation of all numbers in your list to the list; then you have an instance of the subset sum problem. For instance, if your list is 2 40 6 7 6 2, you ask whether a subset of 2 40 6 7 6 2 -2 -40 -6 -7 -6 -2 can sum to 30. That's an instance of the subset sum problem.

If the numbers are not too large, you can use the standard dynamic programming algorithm, and it will be pretty efficient. But this fails if the numbers are large.