# combinatorial optimization? What is the name of this problem and where can I find material for studying it?

I'm looking for material to study the following problem,

Suppose I have $N$ numbers, and I know that the sum of $M$ of those number equals $k$. The goal is to find all combinations of cardinality (is cardinality an appropriate word here?) $M$ that when summed equal $k$.

In addition: All $N$ values are positive.

-
It's the "subset sum" problem (or something very like it). – Gerry Myerson May 4 '12 at 12:58
It is related to the subset sum problem in which the problem is to find one subset which sums to a given integer. Instead, you want to find all such subsets of a given size. – Chris Taylor May 4 '12 at 13:01
If the number are only $\geq 0$, there is a dynamic programming solution O(kM) (for find the number of them, for enumerating them it's O(kM) + O(number of possible set) ). In general the problem is not tractable, so you need to check if there are additional costraint in your problem. – carlop May 4 '12 at 13:34

The answer is: $\binom{k+N-1}{k}$(binomial coefficient). Or $\binom{M+N-1}{M}$, since M=k by your definition.

You questions is equivalent to the question: How many possibilites are there to distribute k indistinquishable balls into N pots?

Here is the argumentation:

g= the number of possiblilities to distribute N balls to M pots, when the pots are not restriced in the number of balls they can hold.

= number of possibilities to distribute M-1 walls and N balls with in a long que of balls and walls (see illustration). (If the row starts with a wall, that means the first pot was empty.)

= number of possibilities to distribute the N balls to N+M-1 pots, which can hold one ball on maximum. (The previous walls are now represented by the empty pots.)

The last problem is the well-known case that is answered by the binomial coefficient. (n+M-1 above n).

It might be a bit tough to follow the idea (and to understand my english), but maybe this picture will help you: https://imgur.com/j2dUC

-
My apologies for being unclear, $M$ is the number of elements which sum to $k$. – csta May 4 '12 at 13:52
Oh, I think it's only now that I understand your question. – Konstantin Schubert May 4 '12 at 13:54