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