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

Java

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

 
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  
newest oldest most voted
Notify of
wkc
Guest

What about negative number ?

foobar
Guest

Setting A[j] to i+1 is really confusing. It should work even if it A[j] is to i, which makes it more clear. Do you guys think setting to i would cause issues?

laxman sharma
Guest

how can we get all possible sets with k partition and equal