Equal Sum Subset Partition Problem
Problem is as specified on LeetCode - Partition Equal Subset Sum
- Array needs to be partitioned into two.
- Both parts should have equal sum.
1. Each partition’s sum will be half of total
Notice that, since we need only two partitions with equal sum, the sum of each part would be half of total sum of array.
So if given array is
We need two partitions,
2. If total sum of array is odd, no partition is possible
This derives from pt 1. An odd number can not be divided equally.
3. The problem now becomes: Is it possible to extract a set of integers from given array whose sum is sumA/2.
4. Problem stated in 3. can be solved using DP