Implementation of partition an array into 2 parts such that the two parts have equal average

Question

I am implementing the approach described in this question for the same problem but I dont think this is working.

For those who dont want to go through the mathematics there, here is the algebra in gist:

Average = Sum(S1)/n(S1) = Sum(S2)/ n(S2) = Sum(Total)/n(Total) 

where n() stands for the number of elements in the array & Sum() stands for the cumulative sum

S1 and S2 are mutually exclusive subsets of array Total. Thus to find the required subset where this condition will hold true, we find Sum(S1) = Sum(Total) * n(S1)/n(Total)

My approach:

#include <bits/stdc++.h>

using namespace std;

bool SubsetSum(vector<int> &A, int Sum)
{
    bool dp[Sum+1][A.size()+1];
    int i, j;
    for(i=0; i<= A.size(); i++)
        dp[0][i] = false; // When sum = 0
    for(i=0; i<=Sum; i++)
        dp[i][0] = 1; // When num of elements = 0
    for(i = 1; i <= A.size(); i++)
    {
        for(j=1; j<= Sum; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j-A[i-1] >= 0)
                dp[i][j] = dp[i][j] || dp[i-1][j-A[i-1]];
        }
    }
    return dp[Sum][A.size()];
}

void avgset(vector<int> &A) {
    int total = accumulate(A.begin(), A.end(), 0); // Cumulative sum of the vector A
    int ntotal = A.size(); // Total number of elements

    int i;
    for(i=1; i<=ntotal; i++) // Subset size can be anything between 1 to the number of elements in the total subset
    {
        if((total * i) % ntotal == 0)
        {
            if(SubsetSum(A, (total * i)/ntotal)) // Required subset sum = total * i)/ntotal
                cout<<"Array can be broken into 2 arrays each with equal average of "<<(total * i)/ntotal<<endl;
        }
    }
}

int main()
{
    vector<int> A = {1, 7, 15, 29, 11, 9};
    avgset(A);
    return 0;
}

This code outputs:

Array can be broken into 2 arrays each with equal average of 12
Array can be broken into 2 arrays each with equal average of 36
Array can be broken into 2 arrays each with equal average of 60

But these answers are wrong.

For example, when subset sum = 12, the corresponding elements will be {11, 1}. Then:

(11 + 1)/2 != (7 + 15 + 29 + 9)/4

Have I misunderstood something here?

score 2 · Answer 1 · answered Sep 07 '18 at 16:16

2

Have I misunderstood something here?

Seems you did.

For given array average always is equal to 12 - total average, first subset average, second subset average.

So you have to check:

1-element subset with sum 12 - does not exist
2-element subset with sum 24 - does exist 9+15
3-element subset with sum 36 - does not exist

and there is no need to check larger sums (>n/2)

answered Sep 07 '18 at 16:16

MBo

77,366
5
53
86

I'm sorry I still dont understand why we have to check for 1-element, 2-element and 3 elements. Could you please elaborate? – user248884 Sep 07 '18 at 20:50
Because this is chosen approach - we are trying to build k-subsets with `ave = subsetsum / k` for all possible k. Really we should check only `k<= n/2` – MBo Sep 08 '18 at 09:38

score 1 · Answer 2 · answered Sep 07 '18 at 16:14

The element number of subset sum should be specified. Find element less equal than n/2 is enough. And there are other errors. Codes as below：

bool SubsetSum(vector<int> &A, int number, int Sum)
{
    bool dp[Sum+1][A.size()+1];
    int i, j;
    for(i=0; i<= A.size(); i++)
        for (j = 0; j <= Sum; j++)
            dp[j][i] = false; // When sum = 0
    dp[0][0] = true; // When num = 0 of 0 elements
    for(i = 1; i <= A.size(); i++)
    {
        for(j=Sum; j>=A[i-1]; j--)
        {
            for (int k = A.size(); k > 0; k--)
                dp[j][k] = dp[j][k] || dp[j-A[i-1]][k-1];
        }
    }
    return dp[Sum][number];
}

void avgset(vector<int> &A) {
    int total = accumulate(A.begin(), A.end(), 0); // Cumulative sum of the vector A
    int ntotal = A.size(); // Total number of elements

    int i;
    for(i=1; i<=ntotal/2; i++) // Subset size can be anything between 1 to the number of elements in the total subset
    {
        if((total * i) % ntotal == 0)
        {
            if(SubsetSum(A, i, (total * i)/ntotal)) // Required subset sum = total * i)/ntotal
                cout<<"Array can be broken into 2 arrays each with equal average of "<<(total * i)/ntotal<<endl;
        }
    }
}

output:

Array can be broken into 2 arrays each with equal average of 24

Hi, Please help me understand: (1). What do you mean by `element number of subset sum`. (2). Why have you trimmed the base case. ie: why only `dp[0][0]` is true and not the whole column. I think the whole column should be true as when we have to make a Sum = 0, there is always 1 option (dont pick anything). (3). Why have you reversed the 2nd for loop `for(j=Sum; j>=A[i-1]; j--)`. (4). Whats the purpose of `for (int k = A.size(); k > 0; k--)` — user248884, Sep 07 '18 at 20:57
1. Find k * avg should match k number, so the partition avg is (k*avg)/k = avg. 2. Only 0 element value as 0 is true. the other value should be processed. 3. not reverse is also OK, make sure j in [A[i-1], Sum]. 4. k means number of elements of the sum value, thus can find specified number elements match the sum value. — zhiwen, Sep 08 '18 at 11:41

Implementation of partition an array into 2 parts such that the two parts have equal average

2 Answers2