Minimum Sum Partition Problem
Given a set of positive integers S, partition set S into two subsets, S1 and S2, such that the difference between the sum of elements in S1 and S2 is minimized. The solution should return the minimum absolute difference between the sum of elements of two partitions.
For example, consider S = {10, 20, 15, 5, 25}.
We can partition S into two partitions where the minimum absolute difference between the sum of elements is 5.
S1 = {10, 20, 5}
S2 = {15, 25}
Note that this solution is not unique. The following is another solution:
S1 = {10, 25}
S2 = {20, 15, 5}
This problem is an optimization version of the partition problem. The idea is to consider each item in the given set S one by one, and for each item, there are two possibilities:
- Include the current item in subset
S1and recur for the remaining items. - Include the current item from the subset
S2and recur for the remaining items.
Finally, return the minimum difference we get by including the current item in S1 and S2. When there are no items left in the set, return the absolute difference between elements of S1 and S2.
Following is the C++, Java, and Python implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> #include <vector> #include <string> using namespace std; // Partition set `S` into two subsets, `S1` and `S2`, such that the // difference between the sum of elements in `S1` and the sum // of elements in `S2` is minimized int findMinAbsDiff(vector<int> const &S, int n, int S1, int S2) { // Base case: if the list becomes empty, return the absolute // difference between both sets if (n < 0) { return abs(S1 - S2); } // Case 1. Include the current item in subset `S1` and recur // for the remaining items `n-1` int inc = findMinAbsDiff(S, n - 1, S1 + S[n], S2); // Case 2. Exclude the current item from subset `S1` and recur for // the remaining items `n-1` int exc = findMinAbsDiff(S, n - 1, S1, S2 + S[n]); return min(inc, exc); } int main() { // Input: a set of items vector<int> S = { 10, 20, 15, 5, 25}; // total number of items int n = S.size(); cout << "The minimum difference is " << findMinAbsDiff(S, n - 1, 0, 0); return 0; } |
Output:
The minimum difference is 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Main { // Partition set `S` into two subsets, `S1` and `S2`, such that the // difference between the sum of elements in `S1` and the sum // of elements in `S2` is minimized public static int findMinAbsDiff(int[] S, int n, int S1, int S2) { // Base case: if the list becomes empty, return the absolute // difference between both sets if (n < 0) { return Math.abs(S1 - S2); } // Case 1. Include the current item in subset `S1` and recur // for the remaining items `n-1` int inc = findMinAbsDiff(S, n - 1, S1 + S[n], S2); // Case 2. Exclude the current item from subset `S1` and recur for // the remaining items `n-1` int exc = findMinAbsDiff(S, n - 1, S1, S2 + S[n]); return Integer.min(inc, exc); } public static void main(String[] args) { // Input: a set of items int[] S = { 10, 20, 15, 5, 25 }; System.out.println("The minimum difference is " + findMinAbsDiff(S, S.length - 1, 0, 0)); } } |
Output:
The minimum difference is 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# Partition set `S` into two subsets, `S1` and `S2`, such that the # difference between the sum of elements in `S1` and the sum # of elements in `S2` is minimized def findMinAbsDiff(S, n, S1=0, S2=0): # Base case: if the list becomes empty, return the absolute # difference between both sets if n < 0: return abs(S1 - S2) # Case 1. Include the current item in subset `S1` and recur # for the remaining items `n-1` inc = findMinAbsDiff(S, n - 1, S1 + S[n], S2) # Case 2. Exclude the current item from subset `S1` and recur for # the remaining items `n-1` exc = findMinAbsDiff(S, n - 1, S1, S2 + S[n]) return min(inc, exc) if __name__ == '__main__': # Input: a set of items S = [10, 20, 15, 5, 25] print('The minimum difference is', findMinAbsDiff(S, len(S) - 1)) |
Output:
The minimum difference is 5
The time complexity of the above solution is exponential and occupies space in the call stack.
The problem has optimal substructure. That means the problem can be broken down into smaller, simple “subproblems”, which can further be divided into yet simpler, smaller subproblems until the solution becomes trivial. The above solution also exhibits overlapping subproblems. If we draw the solution’s recursion tree, we can see that the same subproblems are getting computed repeatedly.
We know that problems with optimal substructure and overlapping subproblems can be solved using dynamic programming, in which subproblem solutions are memoized rather than computed again and again.
Following is the memoized version in C++, Java, and Python that follows the top-down approach since we first break the problem into subproblems and then calculate and store values.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> #include <vector> #include <unordered_map> #include <string> using namespace std; // Partition set `S` into two subsets, `S1` and `S2`, such that the // difference between the sum of elements in `S1` and the sum // of elements in `S2` is minimized int findMinAbsDiff(vector<int> const &S, int n, int S1, int S2, auto &lookup) { // Base case: if the list becomes empty, return the absolute // difference between both sets if (n < 0) { return abs(S1 - S2); } // Construct a unique map key from dynamic elements of the input. // Note that we can uniquely identify the subproblem with `n` and `S1` only, // as `S2` is nothing but `S-S1`, where `S` is the sum of all elements string key = to_string(n) + "|" + to_string(S1); // If the subproblem is seen for the first time, solve it and // store its result in a map if (lookup.find(key) == lookup.end()) { // Case 1. Include the current item in subset `S1` and recur // for the remaining items `n-1` int inc = findMinAbsDiff(S, n - 1, S1 + S[n], S2, lookup); // Case 2. Exclude the current item from subset `S1` and recur for // the remaining items `n-1` int exc = findMinAbsDiff(S, n - 1, S1, S2 + S[n], lookup); lookup[key] = min(inc, exc); } return lookup[key]; } int main() { // Input: a set of items vector<int> S = { 10, 20, 15, 5, 25 }; // total number of items int n = S.size(); // create a map to store solutions to subproblems unordered_map<string, int> lookup; cout << "The minimum difference is " << findMinAbsDiff(S, n - 1, 0, 0, lookup); return 0; } |
Output:
The minimum difference is 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
import java.util.HashMap; import java.util.Map; class Main { // Partition set `S` into two subsets, `S1` and `S2`, such that the // difference between the sum of elements in `S1` and the sum // of elements in `S2` is minimized public static int findMinAbsDiff(int[] S, int n, int S1, int S2, Map<String, Integer> lookup) { // Base case: if the list becomes empty, return the absolute // difference between both sets if (n < 0) { return Math.abs(S1 - S2); } // Construct a unique map key from dynamic elements of the input. // Note that we can uniquely identify the subproblem with `n` and `S1` only, // as `S2` is nothing but `S-S1`, where `S` is the sum of all elements String key = n + "|" + S1; // If the subproblem is seen for the first time, solve it and // store its result in a map if (!lookup.containsKey(key)) { // Case 1. Include the current item in subset `S1` and recur // for the remaining items `n-1` int inc = findMinAbsDiff(S, n - 1, S1 + S[n], S2, lookup); // Case 2. Exclude the current item from subset `S1` and recur for // the remaining items `n-1` int exc = findMinAbsDiff(S, n - 1, S1, S2 + S[n], lookup); lookup.put(key, Integer.min(inc, exc)); } return lookup.get(key); } public static void main(String[] args) { // Input: a set of items int[] S = { 10, 20, 15, 5, 25 }; // create a map to store solutions to subproblems Map<String, Integer> lookup = new HashMap<>(); System.out.println("The minimum difference is " + findMinAbsDiff(S, S.length - 1, 0, 0, lookup)); } } |
Output:
The minimum difference is 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
# Partition set `S` into two subsets, `S1` and `S2`, such that the # difference between the sum of elements in `S1` and the sum # of elements in `S2` is minimized def findMinAbsDiff(S, n, S1, S2, lookup): # Base case: if the list becomes empty, return the absolute # difference between both sets if n < 0: return abs(S1 - S2) # Construct a unique key from dynamic elements of the input. # Note that we can uniquely identify the subproblem with `n` and `S1` only, # as `S2` is nothing but `S-S1`, where `S` is the sum of all elements key = (n, S1) # If the subproblem is seen for the first time, solve it and # store its result in a dictionary if key not in lookup: # Case 1. Include the current item in subset `S1` and recur # for the remaining items `n-1` inc = findMinAbsDiff(S, n - 1, S1 + S[n], S2, lookup) # Case 2. Exclude the current item from subset `S1` and recur for # the remaining items `n-1` exc = findMinAbsDiff(S, n - 1, S1, S2 + S[n], lookup) lookup[key] = min(inc, exc) return lookup[key] if __name__ == '__main__': # Input: a set of items S = [10, 20, 15, 5, 25] # create a dictionary to store solutions to subproblems lookup = {} print('The minimum difference is', findMinAbsDiff(S, len(S) - 1, 0, 0, lookup)) |
Output:
The minimum difference is 5
The time complexity of the above top-down solution is O(n × sum) and requires O(n × sum) extra space, where n is the size of the input and sum is the sum of all elements in the input.
We can also implement the bottom-up version of the memoized solution. The following code shows how to implement it in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <algorithm> #include <numeric> #include <vector> using namespace std; int findMinAbsDiff(vector<int> const &S) { // Find the sum of all elements int sum = accumulate(S.begin(), S.end(), 0); // Create a boolean table to store solutions to subproblems bool T[S.size() + 1][sum + 1]; fill(*T, *T + (S.size() + 1)*(sum + 1), false); // Fill the lookup table in a bottom-up manner for (int i = 0; i <= S.size(); i++) { // elements with zero-sum are always true T[i][0] = true; for (int j = 1; i > 0 && j <= sum; j++) { // exclude the i'th element T[i][j] = T[i - 1][j]; // include the i'th element if (S[i - 1] <= j) { T[i][j] |= T[i - 1][j - S[i - 1]]; } } } // Find the maximum value of `j` between 0 and `sum/2` for which the // last row is true int j = sum / 2; while (j >= 0 && !T[S.size()][j]) { j--; } return sum - 2*j; } int main() { vector<int> S = { 10, 20, 15, 5, 25 }; cout << "The minimum difference is " << findMinAbsDiff(S); return 0; } |
Output:
The minimum difference is 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
import java.util.Arrays; class Main { public static int findMinAbsDiff(int[] S) { // Find the sum of all elements int sum = Arrays.stream(S).sum(); // Create a boolean table to store solutions to subproblems boolean T[][] = new boolean[S.length + 1][sum + 1]; // Fill the lookup table in a bottom-up manner for (int i = 0; i <= S.length; i++) { // elements with zero-sum are always true T[i][0] = true; for (int j = 1; i > 0 && j <= sum; j++) { // exclude the i'th element T[i][j] = T[i - 1][j]; // include the i'th element if (S[i - 1] <= j) { T[i][j] |= T[i - 1][j - S[i - 1]]; } } } // Find the maximum value of `j` between 0 and `sum/2` for which // the last row is true int j = sum / 2; while (j >= 0 && !T[S.length][j]) { j--; } return sum - 2*j; } public static void main (String[] args) { // Input: a set of items int[] S = { 10, 20, 15, 5, 25 }; System.out.println("The minimum difference is " + findMinAbsDiff(S)); } } |
Output:
The minimum difference is 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
def findMinAbsDiff(S): # Find the sum of all elements total = sum(S) # Create a boolean table to store solutions to subproblems T = [[False] * (total + 1) for _ in range(len(S) + 1)] # Fill the lookup table in a bottom-up manner for i in range(len(S) + 1): # elements with zero-sum are always true T[i][0] = True j = 1 while i > 0 and j <= total: # exclude the i'th element T[i][j] = T[i - 1][j] # include the i'th element if S[i - 1] <= j: T[i][j] |= T[i - 1][j - S[i - 1]] j = j + 1 # Find the maximum value of `j` between 0 and `sum/2` for which the # last row is true j = total // 2 while j >= 0 and not T[len(S)][j]: j = j - 1 return total - 2*j if __name__ == '__main__': # Input: a set of items S = [10, 20, 15, 5, 25] print('The minimum difference is', findMinAbsDiff(S)) |
Output:
The minimum difference is 5
The time complexity of the above bottom-up solution is O(n × sum) and requires O(n × sum) extra space, where n is the size of the input and sum is the sum of all elements in the input.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)