Having difficulty in understanding the logic of balanced partitioning

Question

I was solving a problem of balanced partitioning from this link. In this question we have to divide the array in equal parts such that the difference between their sum is least. So, the solution I found out is considering all the cases whether a element will be included in one group or not means we have to try all 2^n cases.

I came up with a solution who divided the array using bit manipulation and I am not getting the logic. I am posting the code below. Someone please tell me how is he dividing the array?

#include<bits/stdc++.h>
using namespace std;
#define N 11

void solve(int a[N])
{
    long long x,y,v1,v2,res,i,j;
    long long val=1<<N;
    res=INT_MAX;
    for(i=0;i<val;i++)
    {
        x=y=v1=v2=0;
        for(j=0;j<N;j++)
        {
            if(i & (1<<j))
            {
                x++;
                v1+=a[j];
            }
            else
            {
                y++;
                v2+=a[j];
            }
        }
        if(abs(x-y)<=1) res=min(res,abs(v1-v2));
    }
    cout<<res<<endl;
}
int main()
{
    int a[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
    solve(a);
    return 0;
}

Answer 1

To optimize you could try to sum the first and last element of each cicle subset, and so avoid to have cicling to all elements number of your subset but cicling only for a number of times equals to the half of your subset size..

In your example, the external cycle iterations remain the same, while the internal are diveded by 2:

(for(j=0; j<(N/2); j++)

and the sum of your grouped subset elements:

v(1|2)+=(a[j] + a[N-j]);