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

Java

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of