Partition problem

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

For example,

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

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

S1 = {1,1,1,2}
S2 = {2,3}.

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

S1 = {3,1,1}
S2 = {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 –
 

1. We include current item in the subset and recurse for remaining items with remaining sum.
 
2. 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++ implementation –
 

Download   Run Code

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. 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 Memoized rather than computed again and again. The Memoized version follows the top-down approach, since we first break the problem into subproblems and then calculate and store values.

We can also solve this problem in bottom-up manner. In the bottom-up approach, 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++ implementation –
 

Download   Run Code

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

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

Notify of
avatar
wpDiscuz