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.


Download   Run Code


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