# number of r-combinations of a set with a sum less than k

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\}$?

-
 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