Partition to K Equal Sum Subsets - source code & running time recurrence relation
Partition a set of positive integers into K subsets, such that the sums of the numbers of each subset are equal.
698. Partition to K Equal Sum Subsets
https://leetcode.com/problems/partiti...
So the function doesn’t just return true or false based on whether it is possible to create K partitions or not. But actually creates those partitions. We assume, these are multi-sets which allow for duplicate values. In other words, the numbers are not required to be unique.
It turns out that if the number of subsets, K, is 3 or more, then the problem is “Strongly NP-Complete”, as proven by Garey and Johnson in their 1979 publication “Complexity results for multiprocessor scheduling under resource constraints” (https://epubs.siam.org/doi/10.1137/02.... Meaning, no pseudo polynomial solution could exist. That is, unless, P=NP.
Last week's episode that tackles the Partition Problem of exactly 2 subsets:
• Partition Problem - 2 subsets of equal sum...
Source code of implementation in Java:
https://bitbucket.org/StableSort/play...
The number of partitions does not have to be some small constant. In fact, it could be as large as n. In that case, the recurrence relation is:
T(n) = n * T(n-1)
T(n-1) = (n-1) * T(n-2)
T(n) = n * (n-1) * T(n-2)
T(n) = n * (n-1) * (n-2) * … T(0) = O(n!)
Which leads to running time of O(n!)
Wikipedia:
https://en.wikipedia.org/wiki/Multiwa...
Not to be confused with
https://en.wikipedia.org/wiki/3-parti...
in which the size of the sets is 3 (you have triplets of numbers that add up to some target). Thanks, @Vadim for clarification.
Written and narrated by Andre Violentyev