Dynamic Programming: Minimum subset difference

Problem Statement:

You are given an array, you need to divide into two subsets that the difference between their sum is minimum.

Example

Input: arr[] = {1, 6, 11, 5}
Output: 2
Subset 1 {1, 6, 5}
Subset 2 {11}

12 – 11 = 1

Solution

This problem is an extension to equal subset sum problem.

Recursion:

Here also, we will have 2 choice for every element. Either to add the element in set 1 or add it in set 2.

So for that, we take 2 variables, include/ exclude.

Then our base case will be, if the list is empty, then we return the absolute difference between the elements.

2. Bottom Up DP

Here also we will take a boolean 2D array of the size [n+1][sum+1].

We fill that array as below:
dp[i][j] = dp[i][j] | dp[i-1][j-arr[i-1]];

Now how do we get the min difference value?

Step 1:

So we know that if we add all the elements we get the total sum, let it be “S”.

Then s1 be the subset 1, s2 be the subset 2.

So s1 + s2 = S

So s2 = S – s1 —-> eq 1

We need to find min absolute difference abs(s2 – s1)

Now substitute equation 1 in s2

it will become abs((S – s1) – s1)

= abs(sum – 2s1)

If s1 == s2, then s1 < (sum/2). This will be same as equal partition subset problem.
But in this question, we need to find the min difference between 2 subsets. It means, s1 lies inside the half of total sum.

So we need to find the best value for s1 that lies inside the first half of the total sum.

Step 2:

Then we will take the last row from our DP table, as we need the total sum. We are concerned with the last row as it will have all numbers from the list as part of partition.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;

int min_sub_set_difference_recursion(int S[], int n, int S1, int S2)
{
    // base case, if the list is empty, then return the absdifference
    if (n < 0) {
        return abs(S1 - S2);
    }
 
    //case 1: Incluse the element in set 1
    int inc = min_sub_set_difference_recursion(S, n - 1, S1 + S[n], S2);
 
    //case 2: Incluse the element in set 2
    int exc = min_sub_set_difference_recursion(S, n - 1, S1, S2 + S[n]);
 
    return min(inc, exc);
}

int min_sub_set_difference_bottom_up(int arr[], int n)
{

    //get total sum
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
    //create boolean DP array 
    bool dp[n+1][sum+1];
 
    // make first column as true as 0 sum is possible with all elements.
    for (int i = 0; i <= n; i++)
        dp[i][0] = true;
 
    // make top row, except dp[0][0], as false. 
    // because with 0 elements, no other sum except 0 is possible
    for (int i = 1; i <= sum; i++)
        dp[0][i] = false;
 
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=sum; j++)
        {
            // If i'th element is excluded if 
          // it is greater than the sum
          if(arr[i-1]>j)
            dp[i][j] = dp[i-1][j];
 
            // If i'th element is included
            if (arr[i-1] <= j)
                dp[i][j] = dp[i][j] | dp[i-1][j-arr[i-1]];
        }
    }
  
    int diff = INT_MAX;
     
    for (int j=sum/2; j>=0; j--)
    {
        if (dp[n][j] == true)
        {
            diff = sum-2*j;
            break;
        }
    }
    return diff;

}



int main()
{
    int S[] = { 10, 20, 15, 5, 25};
    int n = sizeof(S) / sizeof(S[0]);
 
    cout << "The minimum subset difference using recursion is " << min_sub_set_difference_recursion(S, n - 1, 0, 0)<<endl;
    cout << "The minimum subset difference using Bottom Up DP is " << min_sub_set_difference_bottom_up(S, n - 1)<<endl;
 
    return 0;
}

Output:

The minimum subset difference using recursion is 5
The minimum subset difference using Bottom Up DP is 5