# 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?

-
It seems that this may require a set amount of computations. I suggest asking on cstheory.stackexchange.com to determine the computational complexity. This may help you determine how complicated your formula may be. – Matt Groff Nov 29 '10 at 2:06
Wikipedia links to a relevant thesis: diku.dk/users/pisinger/95-1.pdf – Yuval Filmus Nov 29 '10 at 16:43

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)

-
I'd add that there is a formula like way to approach this, but it still relies on brute force. – Matt Groff Nov 29 '10 at 2:30
Thank you. That was a good explanation. – Senthil Kumaran Nov 29 '10 at 2:36
You have reduced the current problem to SUBSET-SUM, which does not prove NP-Hardness of this problem. To prove NP-Hardness, you need to do the reduction the other way. I have removed the -1, though. – Aryabhata Nov 29 '10 at 8:18
Moron is right. It's probably possible to show that this MULTI-SUBSET-SUM problem is also NP-hard, if anyone is really curious they can ask in cstheory. – Yuval Filmus Nov 29 '10 at 16:42

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.

-