3-partition problem extended | Print all partitions

Given an array of positive integers which can be partitioned into three disjoint subsets having same sum and that covers S, print the partitions.


 

For example,

S = { 7, 3, 2, 1, 5, 4, 8 }

We can partition S into three partitions each having sum 10.

S1 = {7, 3}
S2 = {5, 4, 1}
S3 = {8, 2}

 


 

As discussed in the previous post, the 3-partition problem is a special case of Partition Problem where the goal is to partition S into 3 subsets with equal sum unlike the partition problem, where the goal is to partition S into two subsets with equal sum.

This post will extend the previous solution to print the partitions. The idea is to maintain an separate array A[] to keep track of subsets elements. In code below, if value of A[i] is k, then it means that i’th item of S is part of k’th subset.

C++

Download   Run Code

Output:

Partition 0 is: 2 8
Partition 1 is: 1 5 4
Partition 2 is: 7 3

The time complexity of above solution is exponential and it can be optimized using dynamic programming as discussed in previous post.

 
Exercise: Extend the solution to print k-partitions

 
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