# Choosing subsets of a set such that the subsets satisfy a global constraint

We have a set of items $I = \{i_1, i_2, ..., i_n\}$. Each of these items has what we call a p value, which is some real number. We want to choose a subset of $I$, call it $I'$, of size $m$ (for some $m$ with $1 \le m \le n$) such that the average of the p values of the items in $I'$ falls within some specified range, $[p_l, p_u]$. (For example, we might require an average p value between 0.70 and 0.74.) Moreover, we want to do this efficiently.

We hope to do this in O(n) time, but any polynomial time algorithm is good enough. We certainly do not want to just try every possible subset of I of size $m$ and then check whether it satisfies the average p-value constraint.

Finally, we will be doing this repeatedly and we want the subsets chosen to be a uniformly random distribution over all the possible such subsets.

Is there a way of doing this?

Assuming $m$ is an input, your problem is NP-Complete.
Given $A = \\{x_{1}, ..., x_{n}\\}$ for which we need to find a subset of sum $S$, we can create $n$ inputs to your algorithm, with input $A$, $m$ and $p_{L} = p_{U} = \frac{S}{m}$, for $1 \leq m \leq n$.
If $m$ is fixed then the brute force algorithm (which you don't want) is $O(n^m)$ and so has a polynomial time algorithm.