Partition to K Equal Sum Subsets - source code & running time recurrence relation скачать в хорошем качестве

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