Home » Interview coding problems/challenges

Minimum Sum Partition

Minimum Sum Partition: Given an array, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.
Submitted by Divyansh Jaipuriyar, on April 11, 2021

Description: The problem has been featured in interview/coding rounds of many top tech companies such as Amazon, Samsung, etc.

Problem Statement: Given an array, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.

Problem Description: The given problem wants you to find two subsets such that you utilize all the elements of the array and then you are required to find the difference between the two set such that their difference is minimum. It might be possible that it has many subsets satisfying the above criteria but you need to print the difference of that subset whose difference is minimum.

Input: The first line contains an integer 'T' denoting the total number of test cases. In each test case, the first line contains an integer 'N' denoting the size of the array. The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array.

Output: In each separate line print minimum absolute difference.

Example:

Input:
T = 1
N = 5
[5,4,6,9,3]

Output:
1 

Explanation:
S2 = {9,5} And S1 = {4,6,3}. 
S2-S1 = 14-13 = 1

Input:
T = 1
N = 6
[2,7,4,1,8,1]

Output:
1

Explanation:
S2 = {8,4} And S1 = {7,2,1,1}. S2-S1 = 1.

Solution Approach:

This problem is a variation of the subset sum problem. Since here we are not given the size of two subsets, but we are sure that the value in single subset lies between 0 and sum of the array. If we can get the value in a single subset then it is very easy to obtain the value of the other subset. We just subtract it from the total sum to get the sum of values of elements in the second subset.

We need to find the subsets which are present in the array from the value sum/2 to 0, we will check each of these value in the array whether it is possible to obtain the subset or not? To confirm whether we obtained the correct value or not we will use subset-sum logic in this problem:

Therefore, the problem reduces to:

for(int i=sum/2;i>=0;i--)
    if(dp[n][i])
        ans = min(ans,sum-2*i)

Where, dp[n][i] is the value of subset-sum i obtained using n elements. The value of the second subset is obtained as (sum-i). Therefore, the overall difference of two sets is obtained as s2-s1=(sum-i)-i,i.e (sum-2*i), where i need to be as close to sum/2 for the minimum difference.

Time complexity for the above approach in worst cases: O(n*n)

Space complexity for the above approach in worst cases: O(n*n)

Program to illustrate the solution

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n;
        cout << "Enter size of array: ";
        cin >> n;

        ll arr[n];
        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        //sum is the sum of elements of array.
        ll sum = accumulate(arr, arr + n, 0);

        //decallare dp array
        ll dp[n + 1][sum + 1];
        //initialise base case for sum==0
        for (ll i = 0; i <= n; i++)
            dp[i][0] = 1;

        //initialise base cases for sum!=0
        for (ll i = 1; i <= sum; i++)
            dp[0][i] = 0;

        //fill the table in bottom up manner
        for (ll i = 1; i <= n; i++) {
            for (ll j = 1; j <= sum; j++) {
                //if sum>=arr[i-1].
                if (arr[i - 1] <= j)
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i - 1]];
                else //if sum<arr[i-1].
                    dp[i][j] = dp[i - 1][j];
            }
        }

        //initialize temporary ans as maximum
        ll ans = INT_MAX;
        for (int i = sum / 2; i >= 0; i--) {
            //check if the i sum=i is subset sum or not
            if (dp[n][i]) {
                //s1=i,s2=sum-i,i.e(s2-s1)=(sum-i-i)==(sum-2*i)
                ans = min(ans, sum - 2 * i);
            }
        }

        cout << "Final answer: ";
        cout << ans << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 6
Enter elements: 2 7 4 1 8 1
Final answer: 1
Enter size of array: 5
Enter elements: 5 4 6 9 3
Final answer: 1
Enter size of array: 3 
Enter elements: 4 9 3
Final answer: 2