need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer