The partition problem is the task of deciding whether a given set S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2.
Given a set, find out if it can be partitioned into two disjoint subsets such that sum of the elements in both these subsets is equal. Intersection of disjoint sets should be null and union should be the complete set.
For set {7,5,3,5}, sets {7,5} and {3,5} are valid disjoint sets. Also sets {7,5,3,5} and {} are valid disjoint sets. But sets {7,5,3} and {3,5} are not valid disjoint sets since element 3 is present in both of these subsets.
If sum of all the elements in the given set is an odd number say ‘2n+1’, then the best we might be able to do is to partition the given set into two subsets – one with sum ‘n’ and another with sum ‘n+1’. In other words, if sum of all the elements in given set is odd, there is no way the set can be partitioned into two subsets with equal sum.
Now if the sum of all the elements in the given set is an even number say ‘2n’, then all we need to do is to find out a subset say ‘S1’ of the given set such that sum of elements in that subset is ‘n’. The remaining subset(obtained by excluding elements in ‘S1’) then is guaranteed to have sum = ‘n’. For example, the sum of all elements for this set {15,5,15,20,45} is 100. And the subset {5,45} has sum = 50. Now the remaining subset obtained by excluding elements 5 and 45 is {15,15,20} which also has sum = 50.