# 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.

**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**.

**Example with explanation:**

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.

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:

So, initially the function call will be

Where

n-1= index of last element, which isindextotal_sum= total sum of all elements, which issubset1Sum0= subset2SuminitiallyNow, our idea is to check by either including the indexed element in

or by not including. And we will continue doing this recursively until we reach our base case.subset2Let's see the function definition:

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

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

filled up now.dp[n+1][sum+1]= total sum of elementssumHow can we utilize this piece of information as our solution?

Not too tough. If

isdp[i][sum/2]fortrue, it ensures that we have a subset which sumsi= 1 to n. Thus the remaining subset will have to be also of sum(sum/2).(sum/2)This means we can have two equal sum subset.

Now, the point is what if (

) issumodd.Check our second example.

Elements are:1, 3, 4, 8, 5, 6Sum=27which is odd.(sum/2)=13with integer division.dp[6][13] = trueas 8,5 sums to 13.So we would get output

YESbut is it the solution?What's the catch then?

The catch is if

issumodd, the answer will be alwaysNO. You can't partition in two equal subsets.So before doing anything, just check whether the total

issumoddor not. If theis odd simply returnsumelse proceed with the further DP. This would optimize time too.falseC++ Implementation:Output