1
$\begingroup$

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])

$\endgroup$
  • $\begingroup$ Are you allowed to sort them ? $\endgroup$ – azam Jan 16 '16 at 19:20
  • $\begingroup$ Yes, they can be sorted. $\endgroup$ – Marcel Jan 16 '16 at 19:20
  • $\begingroup$ Have a look at the subset sum problem. So no, in general, there is no algorithm that is always fast. $\endgroup$ – Juho Jan 16 '16 at 19:21
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't immediately see how to show NP-hardness of the OP's problem. ​ ​ $\endgroup$ – user12859 Jan 16 '16 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.