# Minimum sum partition problem using dynamic programming | faceprep

Minimum sum partition problem using dynamic programming is discussed here. Given a set of integers, partition the set such the difference between the two set is minimum (absolute difference ) and print the difference.

Sample Input:

4 (number of elements of the array)
14 25 78 96 (array elements)

Sample Output:
7

Explanation:

S1 = {96, 14}
S2 = {78, 25}

Sum of S1 = 110
Sum of S2 = 103

|S1 – S2| = 7

## Algorithm for the minimum sum partition problem

• Divide the set into two parts.
• Consider the following factors while partitioning it.
• Let dp[n+1][sum+1] = {1 if some subset from 1st to i’th has a sum equal to j 0 otherwise}
• Repeat from i = 1 to n
• Repeat from j = 1 to sum of all elements
• So, dp[n+1][sum+1] will be 1 if
1. Sum j is achieved including the i’th item
2. Sum j is achieved excluding the i’th item.
• Let the 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, the sum of S1 is j and it should be closest to sum/2, i.e., 2*j should be closest to sum.

Program for the minimum sum partition problem is given below.

/* C++ program for the minimum sum partition problem */

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n],sum=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
sum+=a[i];
}
bool dp[n+1][sum/2+1];
for(int i=0;i<=n;i++)
dp[i][0]=true;
for(int i=0;i<=sum/2;i++)
dp[0][i]=false;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=sum/2;j++)
{
dp[i][j]=dp[i-1][j];
if(j >= a[i-1])
dp[i][j] |= dp[i-1][j-a[i-1]];
}
}
int diff=INT_MAX;
for(int i=sum/2;i>=0;i–)
{
if(dp[n][i])
{
diff=sum-2*i;
break;
}
}
cout<<diff;
}

Test Case 1

I/P
5
5 7 3 1 9
O/P
1

Test Case 2

I/P
4
14 25 78 96
O/P
7

Test Case 3

I/P
7
45 63 52 41 89 75 65
O/P
18

Test Case 4

I/P
6
14 25 78 96 32 10
O/P
13

Test Case 5

I/P
6
2 2 2 2 2 2
O/P
0