Home » Interview coding problems/challenges

Equal Sum partition

Equal Sum partition: Given a set of numbers, check whether it can be partitioned into two subsets or not such that the sum of elements in both subsets is same. Submitted by Radib Kar, on March 13, 2020

Description

This is a popular interview coding problem which has been featured in interview rounds of Amazon, Oyo rooms, Adobe.

Problem statement

Given a set of numbers, check whether it can be partitioned into two subsets or not such that the sum of elements in both subsets is same.

Input:

First line contains N, the number of elements in the set and the second line contains the elements of the set.

Output:

Print YES if the given set can be partitioned into two subsets such that the sum of elements in both subsets is equal, else print NO.

Explanation with example

    N=5

    Elements are:
    3, 4, 6, 2, 5

    Output: Yes

    The set can be partitioned into two subsets with equal sum,

    Which is, 
    subset1: {3, 2, 5} with sum 10
    subset2: {4, 6} with sum 10

    Another example can be,
    N=6

    Elements are;
    1, 3, 4, 8, 5, 6

    Output would be NO since there is no way to do so.

Solution Approach

We would first check the recursive solution.

Let's create two subset initially where the first subset contains all the elements and the second one is an empty one.

We calculate the total sum and our function is:

    bool EqualPartition(index,subset1Sum,subset2Sum)

So, initially the function call will be

    bool EqualPartition(n-1,total_sum,0)

Where n-1= index of last element, which is index

total_sum= total sum of all elements, which is subset1Sum

0= subset2Sum initially

Now, our idea is to check by either including the indexed element in subset2 or by not including. And we will continue doing this recursively until we reach our base case.

Let's see the function definition:

Function
    EqualPartition(index,subset1Sum,subset2Sum):
        if subset1Sum==subset2Sum //our objective to find
            return true
        if index<0
            return false
        return  EqualPartition(index-1,subset1Sum-arr[index],subset2Sum+arr[index]) || 
                EqualPartition(index-1,subset1Sum,subset2Sum)
End Function

So the recursive definition consists of the case what we discussed above.

    EqualPartition(index-1,subset1Sum-arr[index],subset2Sum+arr[index]) = add the current element(arr[index]) to subset2 
    EqualPartition(index-1,subset1Sum,subset2Sum) = ignore the current element and recur for other elements

So this recursive definition will generate a recursion tree where we can find many overlapping sub problems, hence we would solve by dynamic programing. The solution approach is similar to subset problem.

So we have to create the DP table and fill up the table as per the solution approach in this article.

So, we have dp[n+1][sum+1] filled up now.

sum = total sum of elements

How can we utilize this piece of information as our solution?

Not too tough. If dp[i][sum/2] is true for i= 1 to n, it ensures that we have a subset which sums (sum/2) . Thus the remaining subset will have to be also of sum (sum/2).

This means we can have two equal sum subset.

Now, the point is what if (sum) is odd.

Check our second example.

Elements are: 1, 3, 4, 8, 5, 6
Sum=27 which is odd.
(sum/2)=13 with integer division.
dp[6][13] = true as 8,5 sums to 13.

So we would get output YES but is it the solution?

What's the catch then?

The catch is if sum is odd, the answer will be always NO. You can't partition in two equal subsets.

So before doing anything, just check whether the total sum is odd or not. If the sum is odd simply return false else proceed with the further DP. This would optimize time too.

C++ Implementation

#include <bits/stdc++.h>

using namespace std;

bool equalsubset(vector<int> arr, int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];

    //cout<<sum<<endl;

    if (sum % 2 == 1)
        return false;

    bool dp[n + 1][sum + 1];
    memset(dp, false, sizeof(dp));

    for (int i = 0; i <= sum; i++)
        dp[0][i] = false;
    for (int i = 0; i <= n; i++)
        dp[i][0] = true;
    for (int i = 1; i <= sum; i++) {
        for (int j = 1; j <= n; j++) {
            if (i >= arr[j - 1])
                dp[j][i] = dp[j - 1][i] | dp[j - 1][i - arr[j - 1]];
            else
                dp[j][i] = dp[j - 1][i];
        }
    }

    for (int i = 1; i <= n; i++)
        if (dp[i][sum / 2])
            return true;

    return false;
}
int main()
{
    int t, n, item;

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

    for (int i = 0; i < t; i++) {

        cout << "Enter n, number of elements: ";
        cin >> n;

        vector<int> a;
        cout << "Enter elements: ";
        for (int j = 0; j < n; j++) {
            cin >> item;
            a.push_back(item);
        }

        if (equalsubset(a, n))
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

Output

Enter number of test cases: 2
Enter n, number of elements: 5
Enter elements: 3 4 6 2 5
YES
Enter n, number of elements: 6
Enter elements: 1 3 4 8 5 6
NO