The problem is that you have a set of numbers and you need to divide that set into two subsets where the difference between the sums of the subset is minimal.

Example: a set of numbers {1,5,9,3,8}, now the solution is two subsets, one subset with elements {9,3} and the other {8,5,1} the sum of the first one is 13 and the sum of the second is 13 so the difference between the sums is 0. The result shows the difference between the sums.

Another example: a set of numbers where the difference between the subsets cannot be zero, {9 51 308 107 27 91 62 176 28 6}, the minimal difference between the two subsets is 2.

Can someone please explain this code in detail? I've tried debugging it but i can't figure out how it produces the result. I've been searching for a solution for the problem and this is the code that I stumbled upon. I want to know how the function finds the two subsets, it works great because I've tested it for up to 300 inputs which sum adds up to 100,000.

Many thanks.

p.s Don't worry about the memory leak or that you can only input 300 numbers.

Code:

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
using namespace std;
int BalancedPartition ( int a[] , int n )
{
int sum = 0;
for( int i = 0 ; i < n ; i++)
sum += a[i];
int *s = new int[sum+1];
s[0] = 1;
for(int i = 1 ; i < sum+1 ; i++) s[i] = 0;
int diff = INT_MAX , ans;
for(int i = 0 ; i < n ; i++)
{
for(int j = sum ; j >= a[i] ; j--)
{
s[j] = s[j] | s[j-a[i]];
if( s[j] == 1 )
{
if( diff > abs( sum/2 - j) )
{
diff = abs( sum/2 - j );
ans = j;
}
}
}
}
return sum-ans-ans;
}
int main()
{
int n,result, arr[300];
cin >>n;
for(int i = 0; i < n; i++)
{
cin>>arr[i];
}
result = BalancedPartition(arr,n);
cout <<abs(result); // The difference between the sums of the two subsets
return 0;
}