Balanced Partitioning Dynamic Programming Problem

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;
}

---

Shouldn't set the subsets be {1 3 9} and {8 5} to give each subset a total of 13? Also your program gives a difference of 1 not 2 for {9 51 308 107 27 91 62 176 28 6}. To understand how it produces the result, try making s a pointer to an array of bool instead of int and replace 1 with true and 0 with false when using s. Also note that the number of elements of the s array is 1 more than the sum of the numbers entered. It iterates through the entered numbers from start to finish and for each number entered iterates through the s bool array backwards.

Quote:

---

Can someone please explain this code in detail?

---

Which part of the code don't you understand as it's fairly straightforward c++. If you indicate which line(s) you don't understand I'll try to help to explain what that particular c++ code is doing.

Yeah the example i wrote has many solutions i wrote one of them, yours is one of them too, about the code it is straightforward C++, but i do not see how is the s array used and how through it the solutions are generated (that would be the 2 for loops) :D

clearly, if S is the total sum and P is the sum of a subset then the result R ( = the absolute value of the difference of P and the sum of its complement ) equals |S - 2*P|. The two loops "for( ... for( ... if( s[j] == 1 ){ /*test*/ } ..." just iterates all the possible values of P ( non optimally though ). Then, the "/*test*/" part above just select the P that minimizes R.

if you don't see how the iteration works follow the 2kaud's advice of considering "s" as an array of booleans, then follow the code and write down on paper the sequence of positions of s[] elements that are set true at each iteration.