Minimum subset sum Difference solution | Dynamic Programming | c++

Problem Description

Given an integer array A containing N integers.

You need to divide the array A into two subsets S1 and S2 such that the absolute difference between their sums is minimum.

Find and return this minimum possible absolute difference.

NOTE:

Subsets can contain elements from A in any order (not necessary to be contiguous).

Each element of A should belong to anyone subset S1 or S2, not both.

It may be possible that one subset remains empty.

Problem Constraints

1 <= N <= 100

1 <= A[i] <= 100

Input Format

First and the only argument is an integer array A.

Output Format

Return an integer denoting the minimum possible difference among the sums of two subsets.

Example Input

Input 1:

 A = [1, 6, 11, 5]

Example Output

Output 1:

 1

Example Explanation

Explanation 1:

 Subset1 = {1, 5, 6}, sum of Subset1 = 12
 Subset2 = {11}, sum of Subset2 = 11

Approach:

The problem can be solved using dynamic programming when the sum of the elements is not too big. We can create a 2D array dp[n+1][sum/2+1] where n is number of elements in given set and sum is the sum of all elements. We can construct the solution in bottom-up manner.

The task is to divide the set into two parts. 
We will consider the following factors for dividing it. 
Let 
  dp[n+1][sum/2+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/2+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.

Below is the implementation of above code.

C++

int Solution::solve(vector<int> &A) 

{

    int n=A.size();

    int sum=0;

    for(auto x:A) sum+=x;

    int req=sum/2;

    bool dp[n+1][req+1];

    for(int i=0;i<=n;i++)

    {

        for(int j=0;j<=req;j++)

        {

            if(i==0 && j==0) dp[i][j]=true;

            else if(i==0) dp[i][j]=false;

            else if(j==0) dp[i][j]=true;

            else if(A[i-1]<=j)

                dp[i][j]=dp[i-1][j-A[i-1]] || dp[i-1][j];

            else dp[i][j]=dp[i-1][j];    

        }

    }

    int ans=0;

    for(int i=req;i>=0;i--)

    {

        if(dp[n][i])

        {

            ans=sum-2*i;

            break;

        }

    }

    return ans;

}

Time Complexity = O(n*sum) where n is the number of elements and sum is sum of all elements.

Asked In: Tower Research, Uber

Please share your reviews.

thanks for reading.👍😊

If you like the solution please share with your friends.

and for more dynamic programming question for interview preparation: