Partition Problem - 2 subsets of equal sum, as closely as possible - tutorial and source code

Partition a set of positive integers into two subsets such that the sum of the numbers in each subset adds up to the same amount, as closely as possible. This is an NP-complete problem, dubbed as “the easiest hard problem”. First, we’ll develop a recursive solution with a source code walk through. And then we’ll discuss a completely different solution that uses dynamic programming.

For this problem, we are going to assume that we are dealing with multisets. Meaning, the sets are not restricted to have unique numbers. Therefore, we’ll use arrays to be able to store duplicate numbers.

Partition Problem solved using recursion, source code implementation in Java that creates two partitions:

Dynamic Programming solution, explained in "0/1 Knapsack Problem" tutorial, can be directly applied to solve this problem:

Source code for 01 Knapsack problem using dynamic programming implementation in Java:

Written and narrated by Andre Violentyev

[highruler]

Ahh, the magic of recursion. I struggled with the explenation a bit, but I think i get it now. But like you said, it's a very slow solution so we need to do better. It makes a lot of sense that this problem can be reduced to the Knapsack problem. Time to rewatch your Knapsack video :)

[PallNPrash]

Your videos are just amazing!! Thank you SO much, sir. Your way of explaining hard, complex problems in such a laid-back manner is enthralling to watch!! It's a pleasure subscribing to your channel. Thank you Sir!!!

[aaronzhu]

Thank you so much for this! I have a suggestion for a video maybe; there is barely any info on youtube about bounded knapsack and how to solve it; it took me a good week to understand one of the blogs regarding the topic; could you please make a video on that?

[matamorosa]

Beautiful explanation, I look forward to your future videos

[maridavies]

Elegant explanation - thanks for the nice video

[shyamprakashm]

Congratulation 😁😍.please put some more video of dynamic programming. Subset sum, finding the path

[ds_]

U are so good at explaining the concepts properly

[Wuaners]

What about if result is negative after subtract value of i from target?

[akashagarwal]

Union Find aka DSU could have been also used in such cases?

[gosunov]

There is interesting solution that works in O(S*sqrt(S)) where S is sum of the set

[anant]

Thanks for a great explanation!
Suggested topic: There are some DP problems where we have two sets of size N1 and N2, and we choose N1 as one dimension and 1 << N2 (bitmask for mutually exclusive states) as the other for dp table. Can you explain such problems?

[amirmb_]

Thanks, sir, it helps my understanding a lot :)

[thefuntech]

Sir,
What happened if the weight of the bag is
5^24 then at that condition how would I applied knapsack because knapsack required 0(n*m) auxiliary space I think at that condition I have to go with recursive + backtracking
Is this a right choice ?

[yitshakschlissel]

Suppose your numbers are 1, 10. If you divide the sum of them by 2 you get 5.5 even if you round up the result to 6, then 2 partitions each of size 6 can't contain the number 10.

[ceoofnothing]

the way my professor explained it was very confusing

[nigamsn]

This problem was today's codejam. Very few could solve.