Partition Equal Subset Sum

SOCIAL
----------------------------------------------------------------------------------------------------------------

MUSIC
----------------------------------------------------------------------------------------------------------------
all mine [juen remix] by juen

[KevinNaughtonJr]

Did this help you guys understand dynamic programming?

[Niyatpatel]

That quick change of video frame after submitting the code and getting result 5% better than others was actually funny!!!


But I love your videos, You don't just show solution but show how to come up to the solution and that is the more imprtant. Great Work!!!

[Viewinselym]

Dug around all over the internet for an explanation that makes sense to me. This was the only one I found. Thank you!

[arkocal]

I think it is important to mention that total is a relatively small number because every element in the input is smaller than 100. Without this constraints, the elements could be (in the worst case) the powers of two, and the total could take all the values until 2^n, resulting in a worse complexity of O(n*2^n).

[Smartlib_lol]

Dynamic programming is in some sense avoiding recursion by precomputing values and looping through (bottom up). Saving values from previous recursion or the top down approach is generally just memoization. But in many cases memoization with recursion is far more intuitive.

[Od]

This problem is hard. My brain hurts. Like really trying to figure this out in an interview when you haven’t seen/heard of this this problem!

[christo-j]

I love how you defined there. The memoization is all about reduce the work of unnecessary recursions.

[SameerSrinivas]

Thank you for not only solving the problem but also analyzing complexities! Getting accurate complexities on recursive problems are hard. Well done!

[dmitrykarpenko]

Sounds like it's a knapsack problem, where knapsack size = total / 2 and each number = its value. If filled the knapsack with no space left, return true.

[saadhahmed]

Memoizing is the easy part. My issues are usually with figuring out what to even put as arguments for the recursion.

[algorithmimplementer]

Lets talk about your state string. How do you deal with the state "123-15" and "12-315" in your code as you used empty string to concatenate the index and sum? They product 12315 in both cases. Or these two are same?

[ashleyspianoprogress]

This is the best explanation on YouTube

[InfluentialStudios]

Man, not sure I would have been able to tackle that question, was pretty tough with all of the math behind it. Thanks for the dynamic lesson!

[jaredzhang]

not sure if there is a potential bug caused by the way you compose the map key, eg, index = 1, sum = 23 vs index = 12, sum = 3, the key will be the same, maybe we should add a hyphen in between.

[raiyanrazi]

If we will use an integer matrix for memoization instead of hashmap of type <String, Boolean>, it will be much more efficient

[MG-kspt]

Thanks, brother. Storing the values and using them again is a simple and great approach. It's hard to believe that this simple thing is called dynamic programming. i was always scared of learning DP. I think from now on, I will try to use this technique to recude 2^n time to linear time. Thanks again for helping.

[ployapinon]

Great explanation! Thank you!

Here is a Python version for whoever is looking for ...

class Solution:
def canPartition(self, nums: List[int]) -> bool:
n = len(nums)
total = sum(nums)
if total % 2 != 0: return False

memo = {}

# keep looking for a set that sum up to half of the total
half_total = total // 2
def canPartition(idx, curr_sum):
if (idx, curr_sum) in memo: return memo[(idx, curr_sum)]

if curr_sum == half_total: return True

if curr_sum > half_total or idx >= n: return False

# otherwise, continue to either include the current number or skip this number
foundPartition = canPartition(idx+1, curr_sum+nums[idx]) or canPartition(idx+1, curr_sum)
memo[(idx, curr_sum)] = foundPartition

return memo[(idx, curr_sum)]

return canPartition(0, 0)

[foodscroller]

Best Approach so far....really easy to grasp

[algorithmimplementer]

Excellent explanation of the runtime complexity of both techniques. Thank you :)

[williamalexander]

For a state variable, probably want to use a tuple or comma separated (index, value) in Python or a comma separated string in Java.