1
$\begingroup$

I have been thinking about a better solution to the following problem:

Given a group of numbers, tell if it is possible to get some value, by multiplying all the numbers by $\{0,1,-1\}$ and then add them.

For example,if the given number are $1,3,9,27$ and the value I want to get is $22$. The answer should be yes, because: $$(1)1 + (1)3 + (-1)9 + 27 = 22 $$ One way to do this is to check all possible combinations and look if the sum is the given value, but this takes forever and I have been trying to find a clever way of do it.

Thank you!

$\endgroup$
  • 1
    $\begingroup$ If your set consist of all the powers of $3$, starting with $3^0 = 1$ and ending at $3^n$ for some $n$ (your set is $\{3^0, 3^1, 3^2, 3^3\}$), then it is possible to get all integers in the range from the maximal sum to the negative of the maximal sum, and it's possible in only one way for each integer. This is the number system known as balanced ternary $\endgroup$ – Arthur May 18 '16 at 18:00
  • $\begingroup$ Arthur beat me to it! Do you want a proof of that, or do you want an algorithm for the general case where you have an arbitrary finite set of integers? $\endgroup$ – almagest May 18 '16 at 18:01
  • $\begingroup$ @almagest, Thank you for answering, I do want the algorithm for the general case, not only the one in the example. $\endgroup$ – tiasn May 18 '16 at 18:05
  • $\begingroup$ This is equivalent to the subset sum problem, which is known to be NP-complete. There is a huge literature, and many algorithms, but of course no known polynomial time one. $\endgroup$ – André Nicolas May 18 '16 at 18:05
  • $\begingroup$ @Arthur Thank you for answering, but how about a more general case, where the given numbers are different?for example 27,3,2,1. $\endgroup$ – tiasn May 18 '16 at 18:07

Your Answer

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

Browse other questions tagged or ask your own question.