Partition an array into 2 parts with equal average.

How do you partition an array into 2 parts such that the two parts have equal average? Each partition may contain elements that are non-contiguous in the array.


We need to solve the problem of finding all possible sum for a subset of size k (for 1<=k<=n/2), where n is total number of items.


Let S1 = sum of partition 1
n1 = # of items in partition 1
S2 = sum of partition 2
n2 = # of items in partition 2
S = S1+S2
n = n1+n2
Since, S1/n1 = S2/n2, it implies S1/n1 = S2/n2, which in turn implies (S1+S2)/(n1+n2) = S/n


Now, we populate a table of size (N/2) x N x S, where each entry T[k][i][j] is 1 if we there exists some subset of size k using the set of elements {1,2,...,i} that sum to j. During the computation of this table entries, if we ever found that j/k = S/n, there exists a way to make a partition with equal average. T[k][i][j] can be generated as a recurrence like :


T[k][i][j] = T[k-1][i-1][j-item_i] || T[k][i-1][j] ;


Time complexity: O(N^2*S), 
Space complexity: O(N*S).


Input Array:
int [] A = {2, 4, 4, 5, 6, 6, 7, 8, 9, 12};
Code Output:

Partition 1: 6 1
Partition 1: 57 9