Given a set of positive integers, find if it can be divided into two subsets with equal sum.

S = {3,1,1,2,2,1},

We can partition S into two partitions each having sum 5.

S_{1} = {1,1,1,2}

S_{2} = {2,3}.

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

S_{1} = {3,1,1}

S_{2} = {2,2,1}

**Partition problem** is special case of Subset Sum Problem which itself is a special case of the Knapsack Problem. The idea is to calculate sum of all elements in the set. If sum is odd, we can’t divide the array into two sets. If sum is even, we check if subset with sum/2 exists or not. Below is the algorithm to find subset sum –

We consider each item in the given array one by one and for each item, there are two possibilities –

- We include current item in the subset and recurse for remaining items with remaining sum.

- We exclude current item from subset and recurse for remaining items.

Finally, we return true if we get subset by including or excluding current item else we return false. The base case of the recursion would be when no items are left or sum becomes negative. We return true when sum becomes 0 i.e. subset is found.

## 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> using namespace std; // Return true if there exists a subset of arr[] with given sum bool subsetSum(int arr[], int n, int sum) { // return true if sum becomes 0 (subset found) if (sum == 0) return true; // base case: no items left or sum becomes negative if (n < 0 || sum < 0) return false; // Case 1. include current item in the subset (arr[n]) and recurse // for remaining items (n - 1) with remaining sum (sum - arr[n]) bool include = subsetSum(arr, n - 1, sum - arr[n]); // Case 2. exclude current item n from subset and recurse for // remaining items (n - 1) bool exclude = subsetSum(arr, n - 1, sum); // return true if we get subset by including or excluding current item return include || exclude; } // Return true if given array arr[0..n-1] can be divided into two // subsets with equal sum bool partition(int arr[], int n) { int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; // return true if sum is even and array can can be divided into // two subsets with equal sum return !(sum & 1) && subsetSum(arr, n, sum/2); } // main function to solve partition problem int main() { // Input: set of items int arr[] = { 7, 3, 1, 5, 4, 8 }; // number of items int n = sizeof(arr) / sizeof(arr[0]); if (partition(arr, n)) cout << "Yes"; else cout << "No"; return 0; } |

`Output:`

Yes

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

The problem has an optimal substructure and it also exhibits overlapping subproblems i.e. the problem can be split into smaller subproblems and same subproblems will get computed again and again. We can easily prove this by drawing a recurion tree of above code.

We can use Dynamic Programming to solve this problem by saving subproblem solutions in memory rather than computing them again and again. We solve smaller sub-problems first, then solve larger sub-problems from them. The following bottom-up approach computes T[i][j], for each 1 <= i <= n and 1 <= j <= sum, which is true if subset with sum j can be found using items up to first i items. It uses value of smaller values i and j already computed. It has the same asymptotic run-time as Memoization but no recursion overhead.

## 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 56 57 58 59 60 61 62 63 64 65 66 |
#include <iostream> using namespace std; // Return true if there exists a subset of array[0..n) with given sum bool subsetSum(int arr[], int n, int sum) { // T[i][j] stores true if subset with sum j can be attained with // using items up to first i items bool T[n + 1][sum + 1]; // if 0 items in the list and sum is non-zero for (int j = 1; j <= sum; j++) T[0][j] = false; // if sum is zero for (int i = 0; i <= n; i++) T[i][0] = true; // do for ith item for (int i = 1; i <= n; i++) { // consider all sum from 1 to sum for (int j = 1; j <= sum; j++) { // don't include ith element if j-arr[i-1] is negative if (arr[i - 1] > j) T[i][j] = T[i - 1][j]; else // find subset with sum j by excluding or including the ith item T[i][j] = T[i - 1][j] || T[i - 1][j - arr[i - 1]]; } } // return maximum value return T[n][sum]; } // Partition problem - Return true if given array arr[0..n-1] can // be divided into two subsets with equal sum bool partition(int arr[], int n) { int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; // return true if sum is even and array can can be divided into // two subsets with equal sum return !(sum & 1) && subsetSum(arr, n, sum/2); } // main function to solve partition problem int main() { // Input: set of items int arr[] = { 7, 3, 1, 5, 4, 8 }; // number of items int n = sizeof(arr) / sizeof(arr[0]); if (partition(arr, n)) cout << "Yes"; else cout << "No"; return 0; } |

`Output:`

Yes

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).

**Exercise:** Extend the solution to 3-partitions and also print the partitions.

**References:** https://en.wikipedia.org/wiki/Partition_problem

**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