The "equal subset sum partition problem" is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is the same.
Given an array "arr[]" containing only positive integers, the task is to find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Input: arr[] = {1, 5, 11, 5}
Output: true
Explanation: {1, 5, 5}, {11}
Input: arr[] = {1, 5, 3}
Output: false
Solutions
Method 1: Recursion
This problem is similar to subset sum problem, following are the steps to solve this:
1) Calculate sum of the array, if sum is odd, there can not be two subsets with equal sum, so return false.
2) If sum is even, calculate sum/2 and find a subset of array with sum equal to sum/2. If a subset with sum equal to sum/2 is found return true, otherwise return false.
Complexity
Because this solution tries two possibilities, its time complexity is O(2^n).
In addition, O(N) auxiliary stack space was used for the recursion stack.
Method 2: Memoization
The Memoization Technique is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus decrease time complexity.
We can see that in each recursive call only the value of "n" and "sum" changes, so we can store and reuse the result of a function(..n, sum..) call using a "n * sum" 2-D array.
The 2-D array will store a particular state(n, sum) if we get it the first time.
Now, if we come across the same state (n, w) again, instead of calculating it in exponential complexity, we can directly return its result stored in the table in constant time.
Complexity
The time complexity of this solution is (n * sum).
In addition, O(n * w) auxiliary space was used by the table and O(n) by call stack.