We are given positive integer numbers from $1$ to $10$, and we have to pick $3$ numbers from those $10$ so that the sum of those numbers (repetition of numbers in a sum is not allowed):

$a)$ equals $9$

$b)$ is less then $9$

$a)$ It is clear that those sums are: $ \quad6+2+1=9;\quad 5+3+1=9; \quad4+3+2=9$ . However, I am interested in method or explicit formula for solving this type of problem, do I have to partition the integers by cases, which could be a long process. For example, what if the sum of that $3$ numbers from some given set was supposed to be $857$ instead of $9$, the partitioning of $857$ could last very long.

$b)$ The same slow method of partitioning by cases comes to mind, of course, excluding the integers $10,9,8,7,6$.


The general version of this problem is the "Subset sum problem", and it formulated like this:

Given a (finite) set of numbers $A\subset \mathbb{Z}$ and one number $s\in\mathbb{Z}$, is there a subset $B\subset A$ such that the numbers in $b$ precisely add up to $s$?

This problem is "NP-complete", which roughly means there is no efficient algorithm known for solving it in general. (Though it is an open problem to really prove that none exists). But there are special cases which can be solved using something called "dynamic programming". Also there are approximate algorithms and many other ideas which might help depending on the specific cases. You can read about it here: https://en.wikipedia.org/wiki/Subset_sum_problem.


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.