K-Partition Problem | Printing all Partitions

In k-partition problem, we need to partition an array of positive integers into k disjoint subsets that all have equal sum and they completely covers the set.


 

For example, consider below set

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

1. S can be partitioned into 2 partitions each having sum 30.

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

2. S can be partitioned into 3 partitions each having sum 20.

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

3. S can be partitioned into 4 partitions each having sum 15.

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

4. S can be partitioned into 5 partitions each having sum 12.

S1 = { 2, 6, 4 }
S2 = { 8, 4 }
S3 = { 3, 1, 5, 3 }
S4 = { 12 }
S5 = { 7, 5 }

 


 

k-partition problem is a special case of Partition Problem where the goal is to partition S into two subsets with equal sum. This post will extend the 3-partition solution to find and print k-partitions.

We can start by calculating the sum of all elements in the set. If sum is not divisible by k, we can’t divide the array into k subsets with equal sum. If sum is divisible by k, we check if k subsets with sum of elements equal to (sum/k) exists or not. We can find this by considering each item in the given array one by one and for each item we include it in the i’th subset & recurse for remaining items with remaining sum. We backtrack if solution is not found by including current item in i’th subset and try for (i+i)th subset.

We return true and print the subsets when k subsets each with zero sum are found. For printing the partitions, we maintain an separate array A[] to keep track of subsets elements. If the 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 6 4
Partition 1 is: 8 4
Partition 2 is: 3 1 5 3
Partition 3 is: 12
Partition 4 is: 7 5

 
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
Sort by:   newest | oldest | most voted
wkc
Guest

What about negative number ?

wpDiscuz