Let our numbers $2, 5, 6, 7, 10, 15$ and $k = 15$. I need to find the number of possible options for choosing numbers that form a total of 15. It's $(5, 10), (2, 7 ,6), (15)$. So the answer is 3.
4
-
2$\begingroup$ Welcome to MSE. Please read this text about how to ask a good question. $\endgroup$– José Carlos SantosCommented Jun 13, 2022 at 7:56
-
3$\begingroup$ This looks to me as an example where a simple brute force search would yield the result quickly. It is a different story if you have many numbers: the Knapsack problem is NP-complete which means that, as of today (P vs NP not being solved) there is no efficient algorithm to solve the general case. If there is some regularity in the given numbers, then there may be shortcuts. $\endgroup$– user700480Commented Jun 13, 2022 at 8:07
-
$\begingroup$ As for the manual solution: either $15$ is in the set (and we are done), or $10$ is in the set (and then it is obvious that $6$ and $7$ can't be, and the only way to get additional $5$ is to pick $5$), or $7$ is in the set (and then you have to make up $8$ out of $2,5,6$, which is only possible as $2+6$) or neither $15,10,7$ are in the set (but this is not possible because all the remaining numbers only add up to $13$). Basically - distinguish cases (with the advice to start with the biggest number as this usually yields the solution quicker!) $\endgroup$– user700480Commented Jun 13, 2022 at 8:13
-
$\begingroup$ I wonder if 2,2,2,2,2,5 counts as a solution (i.e., can we reuse numbers?). $\endgroup$– Rebecca J. StonesCommented Jun 13, 2022 at 10:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Do you know generating functions?
Look at the polynomial $$ P(x) = \prod_{i=1}^n(1+x^{a_i}) $$ The coefficient of $x^k$ is the number of possible choices for $k$ as a sum of $a_i$.
