Since the count of items is known a priori (=sizeof(S)), doesn't that mean that the mean and the sum are related in a well defined way? Basically then both critera can be simplified to a single criterion on either sum or mean.
Oh, I missed this detail. In that case for a deterministic result I think you need to look at every possible combination. However, you can order them by the minimum criterion first, and start searching from the smallest to largest, so then the first group than meets the interval criteria is guaranteed optimal.