4
$\begingroup$

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.

  • 0
    If the number are only $\geq 0$, there is a dynamic programming solution O(k*M) (for find the number of them, for enumerating them it's O(k*M) + 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.2012-05-04

1 Answers 1

0

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\choose n$.

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

  • 0
    Oh, I think it's only now that I understand your question.2012-05-04