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.

**C++ implementation –**

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 |
#include <bits/stdc++.h> 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

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.

**C++ implementation –**

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 |
#include <bits/stdc++.h> 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

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