In one of the previous posts, we have looked at the recursive solution for set partitioning problem. In this post, we will cover the dynamic programming approach to solve the same problem. If you have already read the previous post with recursive solution, you can directly skip to 'Algorithm/Insights' section.

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.

Coming back to the problem of finding two disjoint sets with equal sums, an example for that could be subsets {7,3} and {5,5} for set {7,5,3,5}. Sum of elements in both of these subsets is 10. Therefore, the output returned by the program should be 'True'.

Output returned by the program should be 'false' for the set {21,33,37,2}. You can verify that, this set cannot be partitioned into any valid combination of two disjoint subsets such that sum of elements in these subsets is equal.