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

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.

Last week's episode that tackles the Partition Problem of exactly 2 subsets:

Source code of implementation in Java:

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:

Not to be confused with
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

[neerajkrishna]

Calm, detailed, and Excellent Explanation. Thanks a lot.

[move]

your channel is awesome, please keep posting more videos!

[rohanprak]

that animation really helped a lot.
thank you.

[ayushsingh]

Really easy to follow, Liked it a lot!

[chetanraikwar]

Make a whole series on "dynamic programming" 🙏😁
Those animations are very helpful.

[duanwen]

thank you for the crystal clear expaination

[andreiMvisan]

Thank you so much for the solution. The animation helped so much. One correction : the value = ar[i] should be inside the for loop otherwise you can get an

[prae]

Thanks for the video.
I have a practical problem that involves a partition to K Equal Sum Subset (or as close as possible).

Your clear explanations made it clear how to tackle the problem, but I have a constraint that I have no clue how to deal with.
I have to make a partition multiple times, keeping in account previous repartition.
For exemple,
First : Partition of [5, 3, 2] in 3 subset => [5], [3], [2]
Second : Partition of [5, 4, 1] and add them to existings partitions ([5], [3], [2]) => [5, 1], [3, 4], [2, 5]
Etc... N times (once a repartition is done, it can't be changed)

Would you have any advices ?
Thank you again

[FirefoxGuy]

How can you partition to approximately the sum if not exact?

[priyagarg]

Will this solution work if there are negative numbers as well in the array ?

[LesleyGoward]

Hi! I have a question. How it would look in non-recursive way?

[Vaaaaadim]

I had gotten excited when you said this was Strongly NP-Complete for k=3, because this looked doable for a pseudo-polynomial algorithm.
Indeed I had no trouble coming up with one.

But... it appears that the problem you describe isn't actually Strongly NP-Complete.
The problem that you link to a Wikipedia article for in the video description, is not the same problem that is covered in this video.
Given a list of N positive integers, 3-Partition asks you if it's possible to create N/3 subsets which all have equal sum. 3Partition is Strongly NP-Complete.


which asks you to partition a multiset into a fixed number of subsets, and indeed it is known to have a pseudo-polynomial algorithm.

[Majitsu]

this approach gets TLE on leetcode unfortunately