Given an positive integer array with distinct elements, find all possible subset pairs having equal average. How to do this ?

Example: arr={5,10,6,7} Ans: {7},{5,6,10}

Exp: average of first subset=7 average of second subset=(5+6+7)/3=21/3=7

(two subsets for the array which when combined must have all the elements non repeated in the array). Problem is to find all possible pairs and print them. How to do this?

PS: I am not posting my homework stuff and i am learning algorithms. I couldnt find any approach to solve this.

  • 3
    $\begingroup$ "two subsets for the array which when combined must have all the elements non repeated in the array" - are you talking about a partition of an original set into two subsets? $\endgroup$ – HEKTO Apr 16 '16 at 18:59
  • 2
    $\begingroup$ stackoverflow.com/questions/8914961/… $\endgroup$ – HEKTO Apr 16 '16 at 19:00
  • $\begingroup$ yes. split the array into two subsets which has all elements of the array $\endgroup$ – Razor Apr 17 '16 at 6:45

I'm going to take HEKTO's suggestion that you mean that we're decomposing the set into a partition. We start with the observation that in any such decomposition, if the two subsets have the same arithmetic mean, then they must each have the same mean as the original set. To see this, suppose we have decomposed the set into the subsets $|\left\{x_i\right\}| = a$ and $|\left\{y_j\right\}| = b$ where $a + b = n$. If the two subsets have the same average then: $$\frac{\sum_{i=1}^a x_i}{a} = \frac{\sum_{j=1}^b y_j}{b}$$ $$\sum_{i=1}^a x_i = \frac{a}{b}\sum_{j=1}^b y_j$$ Also, observe that: $$\frac{\sum_{i=1}^a x_i}{a} = \frac{(1+a/b)\sum_{j=1}^b y_j}{n}$$ Just distribute the sum on the right and substitute our previous result and you'll see that the average of the $x_i's$ are equal to the average of the whole set.

So, we've elminated a whole lot of partitions for us to look at. I would map each element of the set, $x$, to $x-\mu$, and now we require just that the sum of the elements in a chosen subset add up to 0, and I think a fairly standard dynamic programming approach will work from here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.