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

## Java

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 votes, average: 5.00 out of 5) Loading... 