Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

Given a set of positive integers of size n, how to compute the number of r-combinations of it s.t. the sum of the integers in the combination less than k? Precisely, I have a set $S\subseteq \Bbb N^+$, how to find the number of r-subsets of S s.t. $x_1+x_2+...+x_r\le k$ ? or how to do it with a simplified version, $S=\{1,2,3,...,n\}$?

share|improve this question
I get the feeling this is $NP$-hard. (And so we shouldn't expect to be able to do this in polynomial time in general.) Do you have any bounds on $n$, $r$, $k$, or the size of the integers? – ShreevatsaR Nov 1 '12 at 16:14

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.