Given a set of positive integers S, partition the set S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized.

S = {10, 20, 15, 5, 25 },

We can partition S into two partitions where minimum absolute difference between the sum of elements is 5.

S_{1} = {10, 20, 5}

S_{2} = {15, 25}

Note that this solution is not unique. Below is another solution.

S_{1} = {10, 25}

S_{2} = {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 –

2. We include current item from subset S2 and recurse for remaining items.

Finally, we return minimum difference we get by including current item in S1 and S2. When there are no items left in the set, we return the absolute difference between elements of S1 and S2.

Below is C++ and Java 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 |
#include <iostream> #include <string> using namespace std; // Partition the set S into two subsets S1, S2 such that the // difference between the sum of elements in S1 and the sum // of elements in S2 is minimized int minPartition(int S[], int n, int S1, int S2) { // base case: if list becomes empty, return the absolute // difference between two sets if (n < 0) return abs(S1 - S2); // Case 1. include current item in the subset S1 and recurse // for remaining items (n - 1) int inc = minPartition(S, n - 1, S1 + S[n], S2); // Case 2. exclude current item from subset S1 and recurse for // remaining items (n - 1) int exc = minPartition(S, n - 1, S1, S2 + S[n]); return min (inc, exc); } // main function int main() { // Input: set of items int S[] = { 10, 20, 15, 5, 25}; // number of items int n = sizeof(S) / sizeof(S[0]); cout << "The minimum difference is " << minPartition(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 34 |
class MinPartition { // Partition the set S into two subsets S1, S2 such that the // difference between the sum of elements in S1 and the sum // of elements in S2 is minimized public static int minPartition(int[] S, int n, int S1, int S2) { // base case: if list becomes empty, return the absolute // difference between two sets if (n < 0) { return Math.abs(S1 - S2); } // Case 1. include current item in the subset S1 and recurse // for remaining items (n - 1) int inc = minPartition(S, n - 1, S1 + S[n], S2); // Case 2. exclude current item from subset S1 and recurse for // remaining items (n - 1) int exc = minPartition(S, n - 1, S1, S2 + S[n]); return Integer.min(inc, exc); } // main function public static void main(String[] args) { // Input: set of items int[] S = { 10, 20, 15, 5, 25 }; System.out.println("The minimum difference is " + minPartition(S, S.length - 1, 0, 0)); } } |

`Output:`

The minimum difference is 5

The time complexity of above solution is exponential and auxiliary space used by the program is O(1).

The problem has an 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. Above solution also exhibits overlapping subproblems. If we draw the recursion tree of the solution, we can see that the same sub-problems are getting computed again and again.

We know that problems having optimal substructure and overlapping subproblems can be solved by using **Dynamic Programming**, in which subproblem solutions are *Memo*ized rather than computed again and again. Below *Memo*ized version follows the top-down approach, since we first break the problem into subproblems and then calculate and store values.

Below is C++ and Java 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <iostream> #include <unordered_map> #include <string> using namespace std; // create a map to store solutions of subproblems unordered_map<string, int> lookup; // Partition the set S into two subsets S1, S2 such that the // difference between the sum of elements in S1 and the sum // of elements in S2 is minimized int minPartition(int S[], int n, int S1, int S2) { // base case: if list becomes empty, return the absolute // difference between two sets if (n < 0) return abs(S1 - S2); // construct a unique map key from dynamic elements of the input // Note that can uniquely identify the sub-problem with n and S1 only, // as S2 is nothing but S - S1 where S is sum of all elements string key = to_string(n) + "|" + to_string(S1); // if sub-problem is seen for the first time, solve it and // store its result in a map if (lookup.find(key) == lookup.end()) { // Case 1. include current item in the subset S1 and recurse // for remaining items (n - 1) int inc = minPartition(S, n - 1, S1 + S[n], S2); // Case 2. exclude current item from subset S1 and recurse for // remaining items (n - 1) int exc = minPartition(S, n - 1, S1, S2 + S[n]); lookup[key] = min (inc, exc); } return lookup[key]; } // main function int main() { // Input: set of items int S[] = { 10, 20, 15, 5, 25 }; // number of items int n = sizeof(S) / sizeof(S[0]); cout << "The minimum difference is " << minPartition(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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
import java.util.HashMap; import java.util.Map; class MinPartition { // Partition the set S into two subsets S1, S2 such that the // difference between the sum of elements in S1 and the sum // of elements in S2 is minimized public static int minPartition(int[] S, int n, int S1, int S2, Map<String, Integer> lookup) { // base case: if list becomes empty, return the absolute // difference between two sets if (n < 0) { return Math.abs(S1 - S2); } // construct a unique map key from dynamic elements of the input // Note that can uniquely identify the subproblem with n & S1 only, // as S2 is nothing but S - S1 where S is sum of all elements String key = n + "|" + S1; // if sub-problem is seen for the first time, solve it and // store its result in a map if (!lookup.containsKey(key)) { // Case 1. include current item in the subset S1 and recurse // for remaining items (n - 1) int inc = minPartition(S, n - 1, S1 + S[n], S2, lookup); // Case 2. exclude current item from subset S1 and recurse for // remaining items (n - 1) int exc = minPartition(S, n - 1, S1, S2 + S[n], lookup); lookup.put(key, Integer.min(inc, exc)); } return lookup.get(key); } // main function public static void main(String[] args) { // Input: set of items int[] S = { 10, 20, 15, 5, 25 }; // create a map to store solutions of subproblems Map<String, Integer> lookup = new HashMap<>(); System.out.println("The minimum difference is " + minPartition(S, S.length - 1, 0, 0, lookup)); } } |

`Output:`

The minimum difference is 5

The time complexity of above solution is O(n x sum) where sum is sum of all elements in the array. Auxiliary space used by the program is also O(n x sum).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

This can be easily solve similar to subset sum problem.

1. Lets say total sum of the array is S.

2. take 2d array T[n+1][S/2] and fill the entries similar to subset sum problem

3. now scan last row of T from last until find a true value. Lets say true is found at j then min difference sum value is j

4. we can also print the subset values.

Someone please explain why I cant find overlapping subproblems when I draw a tree for the above example?

The overlapping subproblem property is difficult to visible for this problem due to small input size. You might want to consider larger input.