ronith
11/5/2018 - 7:03 AM

Partition a set into two subsets such that the difference of subset sums is minimum

Given a set of integers, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum. If there is a set S with n elements, then if we assume Subset1 has m elements, Subset2 must have n-m elements and the value of abs(sum(Subset1) – sum(Subset2)) should be minimum.

Example: Input: arr[] = {1, 6, 11, 5} Output: 1 Explanation: Subset1 = {1, 5, 6}, sum of Subset1 = 12 Subset2 = {11}, sum of Subset2 = 11

Algo: The task is to divide the set into two parts. We will consider the following factors for dividing it. Let dp[n+1][sum+1] = {1 if some subset from 1st to i'th has a sum equal to j 0 otherwise}

i ranges from {1..n}
j ranges from {0..(sum of all elements)}

So
dp[n+1][sum+1] will be 1 if 1) The sum j is achieved including i'th item 2) The sum j is achieved excluding i'th item.

Let sum of all the elements be S.

To find Minimum sum difference, w have to find j such that Min{sum - j*2 : dp[n][j] == 1 } where j varies from 0 to sum/2

The idea is, sum of S1 is j and it should be closest to sum/2, i.e., 2*j should be closest to sum.

Minimum Partition.cpp
content_copyfile_download
//https://www.geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum/
#include <iostream>
using namespace std;

int func (int a[], int n, int sum) {
    bool dp[sum+1][n+1];
    for (int i=1;i<=sum;i++)//when there are no elements
        dp[i][0]= 0;
    for (int i=0;i<=n;i++)//when there is 0 sum, it is always possible.
        dp[0][i]= 1;
    for (int i=1;i<=sum;i++) {
        for (int j=1;j<=n;j++) {
            dp[i][j]= dp[i][j-1];
            if (i>=a[j-1])
                dp[i][j]= dp[i][j-1] || dp[i-a[j-1]][j-1];
        }
    }
    int m;
    for (int i=sum/2;i>=0;i--) {
        if (dp[i][n]) {
            m= sum-2*i;
            break;
        }
    }

    return m;
}

int main() {
    int n, sum= 0;
    cin>>n;
    int a[n];
    for (int i=0;i<n;i++) {
        cin>> a[i];
        sum+= a[i];
    }
    cout<<func (a, n, sum)<<endl;
}