Problem Description

Given an integer array arr of size N, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum and find the minimum difference

Example 1:

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

Problem Link

Minimum sum partition | Practice | GeeksforGeeks

Approach

Let S1 and S2 be the two subset partitions of given set S such that

$S1 + S2 = S$

$=> sum1 + sum2 = totalSum$

also,

$abs(sum1 - sum2) = diff$

$=> abs((2*sum1) - totalSum) = diff$

The objective is to minimize the above equation

Code

int minDiffernce(int arr[], int n) 
	{ 
	    int sum = 0;
	    
	    for(int i=0;i<n;i++)
	    sum+=arr[i];
	    
	    vector<vector<bool>> dp(n+1,vector<bool>(sum+1));
	    
	    for(int i=0;i<=n;i++)
	    {
	        for(int j=0;j<=sum;j++)
	        {
	            if(i==0&&j)
	            dp[i][j] = false;
	            
	            else if(j==0)
	            dp[i][j] = true;
	            
	            else if(j>=arr[i-1])
	            dp[i][j] = dp[i-1][j] || dp[i-1][j-arr[i-1]];
	            
	            else
	            dp[i][j] = dp[i-1][j];
	        }
	    }
	    int mindiff = INT_MAX;
	    for(int j=0;j<=sum;j++)
	    {
	        if(dp[n][j])
	        mindiff = min(mindiff,abs(2*j-(sum)));
	    }
	    
	    return mindiff;
	}