I was reading up on the set partition problem on this site of Wikipedia: https://en.m.wikipedia.org/wiki/Partition_problem Among other things, they present a DP approach to solving the equal subset sum problem for 2 subsets by finding a subset that sums to half the total sum of the set. Below the algorithm they state that it is possible to generalize this algorithm to k subsets of equal sums but it is very impractical even for modest input sizes.

However I can't see how this generalization works: with two subsets we have the nice property that if we find a subset that sums to the half of the total sum then we know that the other subset also has to have the same sum and we can answer the question positively.

With the number of subsets bigger than two, however, I don't see how we can find a similar property: let's say the sum of all elements is $S$ and we want to split the set into $k = 3$ subsets. We could see if there is a subset summing to $S/3$, but I'm not sure if this lets us easily split the remaining elements summing to $2S/3$ into two equal parts.

How else could I approach this problem using Dynamic Programming?

  • 1
    $\begingroup$ Did you read the linked paper by Korf? $\endgroup$ – j_random_hacker Jun 2 '18 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.