3-Way Partition Problem
A three-way partition problem is a special case of the equal subset-sum partition problem.
What is the equal-subset partition problem?
An equal subset partition problem determines whether a given set can be partitioned into two or more subsets such that the sum of elements in all the subsets is the same.
What is the three-way partition problem?
Just like the equal-subset problem, in the three-way partition problem, the given set is partitioned into three subsets, such that the sum of all the elements in each subset is equal. This problem’s approach traces the use of recursion and ultimately the smaller overlapping subproblems bring in the use of dynamic programming. Let’s understand the problem.
The Problem Statement
Given a set of positive numbers, find if we can partition it into three subsets such that the sum of elements in all three subsets is equal.
Understanding the problem statement
Let S be a set of 7 integers and the sum of the set is 30.
Input: S = { 7, 3, 2, 1, 5, 4, 8 }
Sum(S) = 30
The goal is to partition S into three separate partitions(s1, s2, s3), each with a sum of 30/3 = 10.
Output:
s1 = { 7, 3 }
s2 = { 5, 4, 1 }
s3 = { 8, 2 }
Conditions:
- All elements should be included in the equally divided subset. No elements should be left.
- None of the elements should be repeated in the subsets.
First Approach: Recursion
We can start by calculating the sum of all the elements in the set. If S(total) is not divisible by 3, we can’t divide the array into three subsets with an equal sum.
If S(total) is divisible by 3, check if 3 subsets with the sum of elements equal to S(total)/3 exists or not. We can find this by considering each item in the given array one by one, and for each item, there are three possibilities:
1. Include the current item in the first subset and recur for the remaining items with the remaining sum.
2. Include the current item in the second subset and recur for the remaining items with the remaining sum.
3. Include the current item in the third subset and recur for the remaining items with the remaining sum.
The base case of the recursion would be when no items are left. We return true when 3 subsets, each with zero-sum, are found.
We can optimize our code by calling case 2 only if case 1 doesn’t result in a solution, and case3 only if cases 1 and 2 don’t result in any solution.
Second Approach: Dynamic Programming
Dynamic programming, in short, is just to add a dictionary to the recursion function so that it can store the results of the search before space is utilised.
If the subsequent search returns to the same search space, for example:
If isSubsetExist(2, 1, 10, 10) was called the second time, the dictionary can directly return the result of isSubsetExist(2, 1, 10, 10) without searching down the branch of it again.
While the repeat of search isSubsetExist(2, 1, 10, 10) is harder to see in this partitioning problem.
Output:
Time Complexity
The time complexity of dynamic programming is O(n x sum³) where n is the size of input and sum is the sum of all elements from the input while the recursion-only solution is exponential.
Authors:
Rushabh Shah
Aryan Sharma
Dhruv Singhal
