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
    It's the "subset sum" problem (or something very like it).2012-05-04
  • 2
    It is related to the [subset sum problem](http://en.wikipedia.org/wiki/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.2012-05-04
  • 0
    [Here's a StackOverflow thread about this problem](http://stackoverflow.com/questions/8916539/sum-subset-with-a-fixed-subset-size)2012-05-04
  • 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
    My apologies for being unclear, $M$ is the number of elements which sum to $k$.2012-05-04
  • 0
    Oh, I think it's only now that I understand your question.2012-05-04