Find all possible subset pairs in an array having equal average

Question

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.

Answer 1

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.