Minimum multi-subset sum to a target This is some sort of standard puzzle, which many do it using trial and error or brute-force method. The question goes like this, given the numbers, 11,13,31,33,42,44,46 what is choices of numbers (a number can be chosen more than once) so that sum adds up to 100.
Is there a formula like way or approach to this other than brute force only?
 A: Assuming that the numbers are positive integers,
This is closely related to the Frobenius Coin Problem which says that there is a maximum number $\displaystyle F$ (called the Frobenius number) which is not representable. It is NP-Hard to find out the Frobenius number when there are at least $\displaystyle 3$ numbers.
For a formula like approach to determine if such a representation is possible or not, you can use generating functions, which can be used to give a pseudo polynomial time algorithm, polynomial in size $\displaystyle W = n_1 + n_2 + \cdots + n_k$.
If the numbers are $\displaystyle n_1, n_2, \dots, n_k$ and you need to see if they can be summed to $\displaystyle S$ then the number of ways it can be done is the coefficient of $\displaystyle x^S$ in
$$\displaystyle (1+x^{n_1} + x^{2n_1} + x^{3n_1} + \cdots )(1+ x^{n_2} + x^{2n_2} +  x^{3n_2} + \cdots ) \cdots (1 + x^{n_k} + x^{2n_k} + x^{3n_k} + \cdots )$$
$$\displaystyle  = \dfrac{1}{(1-x^{n_1})(1-x^{n_2}) \cdots (1-x^{n_k})}$$
Using partial fractions this can be written as
$$\displaystyle \sum_{j=1}^{m} \dfrac{C_j}{c_j - x}$$
where $\displaystyle C_j$ and $\displaystyle c_j$ are appropriate complex numbers and $\displaystyle m \le n_1 + n_2 + \cdots + n_k$.
The coefficient of $\displaystyle x^S$ is thus given by
$$\displaystyle \sum_{j=1}^{m} \dfrac{C_j}{c_j^{S+1}}$$
which you need to check is zero or not.
Of course, this might require quite precise floating point operations and does not actually tell you what numbers to choose.
A: SUBSET-SUM is NP-complete, so in general it's difficult to tell even if there is a choice of numbers that adds up to a given target.
EDIT: Moron has raised the valid point that numbers can be reused.
We therefore replace each number $x$ with a sequence $x,2x,4x,\ldots,2^kx,\ldots$, stopping before reaching a number larger than our target.
Let's carefully analyze the blowup in size. Suppose the original numbers $x_i$ had size $l_i$, and the target $T$ had size $L$. We replace each number $x_i$ with $L$ numbers of size at most $L$, and so the new size is $$\sum_i L^2 + L \leq L^2 (\sum_i x_i + L),$$ so the blowup is at most cubic, and in particular polynomial. So the problem is still NP-hard (it is trivially in NP): no, since the reduction is in the wrong direction... (thanks, Moron, for noticing)
