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