Suppose that you have a multiset of positive integers $I$.
$I$ is not given, but it is known that the sum over all elements of $I$ = $k$.
(e.g. if $I$={2,5,7} then k=14 is given, but I is unknown).
We are also given another integer $r$.
$S\subseteq I$ will be called $r-minimal-subset$, if $sum(S)>r$,
and for every $x\in S$, $sum(S$\{x}$) \leq r$.
For example, if $I$={1,3,3,5,7,8} and r=10,
then {3,3,5} and {1,3,7} are r-minimal-subset, but {5,7,8} is not (as the subset {7,8} 's sum is 15. {7,8} is a r-minimal-subset).
What is the the best upper bound we can give on the number of $r-minimal-subsets$ of I?
(In this setting, we get is $(r,k)$, while $I$ is being chosen by an adversary).
~~~~~~~~~~~~~~~~~~~~~~~~~~
Edit: Hmm, sorry for the question.
Obviously the answer is $k \choose r+1$, for I={1,1,..,1}, $|I|=k$. It doesn't let me answer the question, so you could go ahead :/.