Dynamic Programming: Equal Sum Partition Problem
Dynamic Programming Problem #3 : Equal Sum Partition
Before starting up with the Equal Sum Partition Problem, I would highly recommend you to read this introduction to Dynamic Programming. Here I have covered the basic method on how to approach a DP based problem. We will be using the same concepts to solve the Equal Sum Partition Problem. I’d also highly recommend you to go through the Subset Sum Problem since it’s the parent problem for Equal Sum Partition Problem.
With that being said, let’s get started.
1. What is Equal Partition Sum Problem ?
Given a set of N non-negative integers, determine if the set can be partitioned into two subsets such that the sum of the elements in each of the two subsets is equal. Return 1 if there exists such partition, otherwise return 0.
Let's say we havenums = [2, 8, 9, 3]Thus here subsets {2, 9} and {8, 3} form such partitions where the sum of elements in the both the sets is equal. Which in this case is 2 + 9 = 11
8 + 3 = 11Thus we return True
2. How should we approach ?
If you would have read this article on Subset Sum Problem, then you would be easily able to tell the reason why that problem is it’s parent. The current problem is a slight variation of the above stated parent problem.
Now, let’s assume that the sum of the elements in the given set is S.
Thus if there is a possibility of a partition which results in equal sum subsets then they must follow the following relation
S = s1 + s2
where s1 and s2 are the sum of elements of subset 1 and subset 2 respectively. Also s1 is equal to s2.
S = 2*s1
or
S = 2*s2
Thus we can easily say that if the sum S of the set is an even number, then there exists a possibility that a partition matching the above stated conditions can be made. Otherwise for a case where S is odd, no such partitions can be made.
Thus the whole problem reduces to finding Subset Sum Problem for the given set with the target sum = S/2.
So here’s how the solution for the same would look like
I would highly recommend you to go through the Subset Sum Problem (this will be suffice) in order to fully understand how to write the above given solution. With this we have come to an end of Equal Sum Partition Problem. You can practice coding it yourselves here.
Thank You
