Given an array of $n$ integers $A$, and some value $m$, determine if it is possible, by using certain amounts of each element, to get a total sum equal to $m$. Consider that you can use any amount of any of the elements.

This is sort of like the subset sum problem, but in this case that sum can contain elements multiplied by some factor, and this factor has no upper-bound. I'm struggling quite a bit with this problem, so does anyone know how can I solve it?

  • 1
    $\begingroup$ Have you tried proving that this problem is NP-complete? $\endgroup$ Apr 29, 2018 at 16:01
  • $\begingroup$ No, but i don´t think it is because this is an exercise in my competitive programming class. Either that or i´m misinterpreting the problem. $\endgroup$ Apr 29, 2018 at 16:04
  • 1
    $\begingroup$ If you're allowed to use negative integer amounts, then the problem is easy. Otherwise, I believe that it's NP-complete. You can try adapting the dynamic programming algorithm to solve it for small $m$. $\endgroup$ Apr 29, 2018 at 16:05
  • 2
    $\begingroup$ You can reduce your problem to the usual subset sum by replacing each integer $k$ by $k,2k,4k,\ldots,2^{\lfloor \log_2 m \rfloor}k$, and now use any technique you know for subset sum (dynamic programming, meet in the middle) in order to solve your problem. $\endgroup$ Apr 29, 2018 at 18:32
  • 1
    $\begingroup$ It's also not quite clear what your goal is, as you pretty much only state the problem. Do you want to give and algorithm or analyse the complexity? What have you tried and where did you get stuck? $\endgroup$
    – Raphael
    Apr 29, 2018 at 20:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.