Answer 1

Hi Pandurand,

What you just described is an NP-Hard problem know as Subset Sum.

Problems in the NP-Hard class are among the most difficult ones and to this date no polynomial time algorithms are known for them. In the worse case they usually require exponential execution time.

In the case of the Subset Sum, there exists a Pseudo-polynomial time algorithm based on Dynamic programming. For more information please see: https://en.m.wikipedia.org/wiki/Subset_sum_problem