Equal Sum Partition Problem

Suppose we have an array arr, {1,2,3,4,5}
We have to create two subset from the above array, let’s call those subset A and B, so the sum of subset(A) should be equal to subset(B).
Elements cannot be repeated, once allocated to any of the subset.

For example, if 1 is assigned to subset A, we cannot assign it to subset B again.

Expected Output, return true if such partition is found or return false.

Naive Approach
Let’s suppose, the sum of array is S. So reading the problem statement, we have two divide arr into two equal subset. Hence Subset A and Subset B=(S/2).

For this approach, we generate all the subset of the given arr and check if it sums up to be (S/2).

Also since subset A and Subset B, will be divided in two parts the sum of array arr should be a even number.
In case the sum of array arr is odd, no such partition exist.

Time Complexity for this approach will be O(2^n) which is why this is very expensive approach.

Dynamic Programming
Think about this problem again, we just need to work on one subset.
and Calculate its sum. If its value=(Sum/2) good for us.
Therefore, we apply the approach of Subset Sum problem where you goal is to find an subset of array which sum to the given integer.
What is our given integer here, (Sum/2)

Initialize a matrix whose number of column= sum+1, why 1 because we are also including 0.
Step 1) Now fill the first column with True, because we know 0 sum can always be found using empty set.