Partition Equal Subset Sum - Dynamic Programming - Leetcode 416 - Python

  Рет қаралды 135,908

NeetCode

NeetCode

Күн бұрын

Пікірлер: 166
@NeetCode
@NeetCode 3 жыл бұрын
💡 DP Playlist: kzbin.info/www/bejne/bWTVZH6Nnqqpr80
@mr6462
@mr6462 2 жыл бұрын
It's an interesting yet very important observation that the two subsets must equal to half of the total sum. Somehow I didn't think of this during my thinking process, was too obsessed with finding a representation and storing the subset sums in a hash map. Interesting.
@expansivegymnast1020
@expansivegymnast1020 Жыл бұрын
Same. Makes so much sense.
@falcomomo
@falcomomo Жыл бұрын
My god, sometimes I am so dumb
@ivivivivviviviviviviviv
@ivivivivviviviviviviviv Ай бұрын
Thank you for this comment
@minciNashu
@minciNashu 2 жыл бұрын
there's no need to iterate backwards, and there are some optimizations 1, break early with False if nums[i] is greater than target, or with True if equal to target 2, break early with True instead of adding something to DP that matches target 3, there's no need to store in DP sums which are greater than target
@mahmoudalsayed1138
@mahmoudalsayed1138 Жыл бұрын
My thinking exactly, I was puzzled by the fact that he iterated backwards
@strawberriesandcream2863
@strawberriesandcream2863 Жыл бұрын
wrote the code out for your simplification: class Solution: def canPartition(self, nums: List[int]) -> bool: if sum(nums) % 2: return False target = sum(nums) // 2 dp = set() dp.add(0) for i in range(len(nums)): if nums[i] > target: return False dpClone = dp.copy() for t in dp: if (t + nums[i]) == target: return True if t + nums[i] < target: dpClone.add(t + nums[i]) dp = dpClone return False
@truongkimson
@truongkimson 6 ай бұрын
he said you can do it in forward order, he just likes it backward
@ziyuzhao2442
@ziyuzhao2442 8 күн бұрын
@@mahmoudalsayed1138 if you have watched his video, he loves backwards for no reason
@msh104utube
@msh104utube 3 жыл бұрын
This solution was the best from what I've seen so far: fast, short and well explained.
@AnikaRathi9
@AnikaRathi9 2 жыл бұрын
We can check if (t + nums[I]
@mohammadhoseinabbasi9993
@mohammadhoseinabbasi9993 2 жыл бұрын
Honestly how the hell is someone supposed to come up with such a solution in half an hour during an interview?
@adityabohra6991
@adityabohra6991 5 ай бұрын
Exactly, like what the hell are people on any new drug
@fabricator.cap.hill.seattle
@fabricator.cap.hill.seattle 5 ай бұрын
It's these irritations of life that fuel my existentialism.
@EE12345
@EE12345 4 ай бұрын
Easy, know the solution already and pretend it's your first time seeing it. Just like most of these bs questions lol
@dingus2332
@dingus2332 3 ай бұрын
an easier way to solve this problem is first find the target , then do a targetSum algo on it , its works ... , this bottom up approach is tougher
@cout...codingandstuff
@cout...codingandstuff 3 ай бұрын
Bro look at some Competitive Programming problems, and you'll see these are baby-level in difficulty, you don't even need to use C++ to pass the constraints of these problems.
@siqb
@siqb 3 жыл бұрын
Awesome video mate! Here are a few things might help others (helped me at least): 1. Variable "dp" could perhaps be renamed "subsums". The problem then sounds a lot like the 2-sum problem where the remaining summand is looked up and if it exists then you have your solution. The "remaining summands" here are the subsums from earlier loops. 2. The simplicity of zero being added to "dp" hides away a lot of complexity of code. This is what enables all possible subsum combinations. The addition of 0. 3. This was hardest for me: We loop all the way to the end. I mean the whole array can't be in one half so why do we do that? Well this is closely connected to #2. Since we need to search for the right subset, well it could be or include the last element too so that's why. Thanks again for making such great videos. As another small optimization to pushing the if-clause up, we could also do the following: if s + nums[i]== target: return True elif s + nums[i] < target: # this condition should keep subsequent loops shorter since they needlessly wont go through subsums > target. nextDP.add(s + nums[i])
@CostaKazistov
@CostaKazistov 2 жыл бұрын
Perfect! I also thought DP might be a bit of a confusing name for a set. Subsums definitely makes more sense.
@navaneethmkrishnan6374
@navaneethmkrishnan6374 2 жыл бұрын
I agree with the dp naming part. Why we get confused is because these elements are not contiguous subproblems. Sub problems in this problems repeat after an interval. The idea to solve this problem theoretically is DP, but practically, it's is just an intuitive approach.
@SmoothCode
@SmoothCode 2 жыл бұрын
This was by far the best code that I could actually mentally follow along with and not be totally lost in the middle.
@Darkmatterkun
@Darkmatterkun Жыл бұрын
The solution you wrote in the end will have 2^N time complexity because you have to generate all the possible subset sums using that method.
@KietNguyen-jq7ql
@KietNguyen-jq7ql Жыл бұрын
This is exactly what I thought
@Dhruvbala
@Dhruvbala 3 ай бұрын
This was a clever approach. Simpler than using a 2d array -- as do most tutorials on KZbin
@ruthviks
@ruthviks 11 ай бұрын
With slight changes into the code, I framed the following code and it beats 95% other submissions by time and 58% by space. Hope it is useful! Hey by the way, the walkthrough was very useful and easy to understand. Thank you for making such videos class Solution: def canPartition(self, nums: List[int]) -> bool: if sum(nums) % 2: return False seen = set([nums[-1]]) sum_val = sum(nums) // 2 for i in range(len(nums) - 2, -1, -1): temp = set() for num in seen: temp.add(num + nums[i]) seen = seen.union(temp) if sum_val in seen: return True return False
@cleancodeET
@cleancodeET 5 ай бұрын
why you in reverse way? just does not make sense it works in both way
@restindev
@restindev 3 жыл бұрын
Ugh. Thanks lol. Some of these DP problems are so gross, and I am not really sure where in practice this problem should actually arise.
@zzzzzzzjsjyue2175
@zzzzzzzjsjyue2175 9 ай бұрын
Why is the memory complexity not O(2^n)? we are in practice finding every subset and checking the sum?
@sonnguyen8819
@sonnguyen8819 6 ай бұрын
when using set, you remove duplicate so it's not O(2^n) it's max O(sum(nums)) because it's all possible value
@zzzzzzzjsjyue2175
@zzzzzzzjsjyue2175 6 ай бұрын
@@sonnguyen8819 oh yes you’re correct thanks
@andrepinto7895
@andrepinto7895 2 жыл бұрын
You really like to start from the end and go backwards! literally zero reasons to do that here :D
@alirezaaghamohammadi2955
@alirezaaghamohammadi2955 3 жыл бұрын
by far the best explanation I've found, thank you so much for posting this and doing a great job explaining all the steps.
@juliramoos
@juliramoos 8 ай бұрын
I don't get why the memory complexity is limited to target. We're iterating over the entire array and at each iteration we double the number of elements in the set. Doesn't this add up to 2^n?
@truongkimson
@truongkimson 6 ай бұрын
yeah neetcode dropped the ball on this one. Space complexity is limited to target only if we reject entries > target i.e. only add t + nums[i] to set if t + nums[i]
@ismailkaracakaya260
@ismailkaracakaya260 2 жыл бұрын
You are using 2 sets which is a bad idea, taking so much space , note dp is all about caching. Do this: class Solution: def canPartition(self, nums: List[int]) -> bool: if sum(nums) % 2 != 0: return False target = sum(nums) // 2 dp = [False] * (target + 1) dp[0] = True for num in nums: for i in range(target, num - 1, -1): dp[i] = dp[i] or dp[i - num] return dp[-1]
@markolainovic
@markolainovic Жыл бұрын
Can you explain the reasoning behind this? Edit: nvm, figured it out, also keeps track of partial sums, much like the OP's solution. Thought it does seem more elegant than the given solution, the odd thing is, it's actually over 2x times slower! I wonder why....
@tusharmore3860
@tusharmore3860 2 ай бұрын
@@markolainovic Yes because it is finding out the sum/ possibility to exist the target from each no which ultimately useful to build the table.
@swapnilsdt
@swapnilsdt 2 жыл бұрын
@NeetCode really liked your explanation. But for the optimal solution wouldn't the worst case time complexity and space complexity when the sum doesn't exist in your exhaustive sum set be O(2^n)? Consider the example where the elements don't add up to existing elements in the set - (10,100,1000,10000)
@mehershrishtinigam5449
@mehershrishtinigam5449 Жыл бұрын
Yes.. the "optimal solution" is literally brute force... bruh.
@DavidDLee
@DavidDLee Жыл бұрын
Yes, there's a mistake in the analysis part. Space complexity is O(2^N). Every loop, in worst-case, doubles the size of the set, except for duplicates.
@sreenidhisreesha
@sreenidhisreesha Жыл бұрын
@@DavidDLee there is mistake in timecomplexity part as well. the size of the set can be 2^N and the loop can run for 2^N. making the time complexity O(n * 2 ^N) which is O(2^N)
@truongkimson
@truongkimson 6 ай бұрын
you're right. technically his solution's time complexity is O(2^n). He basically went through the entire decision tree and calculated every possible sum. The reason his solution didn't time out is because, by using a set, duplicate subsums are removed. However, these duplicate sums are there "by chance", not because they are cached like in DP approach. So practically, his solution is still faster than brute force. If you design a test case careful enough for his solution, his runtime can be as bad as brute force
@spano1723
@spano1723 9 ай бұрын
Why would you iterate backwards?
@danielsun716
@danielsun716 Жыл бұрын
This is the 4th time to watch this video. Leetcode's solution is actually telling us to list the bottom result in the decision tree. That is what I got from the 4th watching. Thanks.
@susantamohapatra2973
@susantamohapatra2973 Күн бұрын
This is a beautiful and simple solution. But what about using a dictionary instead of a set ? - Shouldn't that reduce the time complexity from O(n * sum(nums)) to O(n) ?
@jing6934
@jing6934 2 жыл бұрын
you can use dp |= nextDP the set union instead of dp = nextDP to avoid nextDP.add(t)
@ax5344
@ax5344 3 жыл бұрын
It feels like "the easier the code, the harder the thinking process". Thanks! I was trying to code with dp and backtracking+memoization and found the code hard and prone to error. This solution does have a clear code but to arrive at this idea is hard.
@NeetCode
@NeetCode 3 жыл бұрын
That's definitely true, I would prefer to code out the memorization solution and then code the DP solution. Main reason I don't in the videos is to keep the video concise.
@DavidDLee
@DavidDLee Жыл бұрын
There are a two problems in this solution: 1. The space complexity is all wrong. It will be O(2^N) in the worst-case. Only duplicates reduce space usage. Every inner loop duplicates the size of the set. 2. Building a new set and copying older values into it makes the solution also O(2^N), because that's how many values we can end-up storing in the set. It is a much better idea to only add the new values, outside the inner loop.
@abirbhavdutta5687
@abirbhavdutta5687 Жыл бұрын
Actually the space complexity can be reduced by simply not storing the value if t + nums[I] > target. In this case the set will be at most O(target) and the time complexity will be O(N*target). But since he has not done that, his solution is potentially O(N * 2^N)
@vishweshganapathy8189
@vishweshganapathy8189 11 ай бұрын
time complexity appears to be 2^N, since all the values are generated and stored - a loop for every value
@Kaushikraj9845
@Kaushikraj9845 2 жыл бұрын
Thanks..I was wondering why we have to check sum of any array elements can reach to target=total_sum/2 ..Another Eg: 1,4,5, Sum=10 2,3,4,5 Sum=14 Yes 2,3,4,5,2 Sum=16 Yes 18,2 Sum=20 No ..The last example gave me why we have to check only for target..
@yuansyunyeh9008
@yuansyunyeh9008 Жыл бұрын
Because we can only get the two subsets. Then, the two subsets must be equal. So, the sum of the subset must be the halve of the sum.
@kaci0236
@kaci0236 3 ай бұрын
since you have to count sum of nums before you start your algorithm (which is a n time complxity), isn't the time complexity n + n * sum(nums)?
@obitonamizake4539
@obitonamizake4539 2 жыл бұрын
Thanks a lot, can you tell me how do you convert a decision tree into recursion?
@JefferyChiang-l3x
@JefferyChiang-l3x 2 жыл бұрын
Thanks for the great explanation! Though I think the third solution is O(n*2^n). The outer loop is O(n) and the inner loop is O(2^n).
@JefferyChiang-l3x
@JefferyChiang-l3x 2 жыл бұрын
I figure it out... total number of sums in the hashset will be
@feeltheheat96
@feeltheheat96 2 жыл бұрын
i still don' understand, i tried to analyse it and i got 2^n?, what do you mean by the hashset will be smaller than total sums
@TJ-zs2sv
@TJ-zs2sv 2 жыл бұрын
The time complex of last solution is 2 ^ (n+1) (1 + 2 + 4 + 8..... 2 ^n) ---> G.P , but space is O ( target)
@pepehimovic3135
@pepehimovic3135 2 жыл бұрын
@@TJ-zs2sv The space cannot possibly be O(target) Just think of an example with 1 very large number. Given the array [1, 2, 997], the target will be 500. The set holding the combinations will be [0] [0, 1] [0, 1, 2, 3] [0, 1, 2, 3, 997, 998, 999, 1000] 8 elements. How can you argue O(target)?
@utsavmathur1478
@utsavmathur1478 3 жыл бұрын
Brother, your videos have been of great help! It's the best explanation I've seen so far
@guimauve_
@guimauve_ Жыл бұрын
If we remove the odd sum check at the begining then the following test does not pass (and probably others): [1,2,3,5] I can't figure out (yet) if this is expected or not
@berkeevrensevdi1788
@berkeevrensevdi1788 2 жыл бұрын
I do not understand how Space Complexity was improved by using set. If we use set like this, does not it have O(2^n) space complexity?
@MinhNguyen-lz1pg
@MinhNguyen-lz1pg 2 жыл бұрын
Set does not contain duplications, similar how we cache it. For each number going backward, he calculate the sum using the already calculated sum from the set, thus does not has to calculate the same "sub-sum" every time
@berkeevrensevdi1788
@berkeevrensevdi1788 2 жыл бұрын
Oh you are right. When we obtain the same total as we did earlier, it will not increase the set size and in the worst condition, we have sum(nums) different totals. Thank you for explanation :)
@fadsa342
@fadsa342 Жыл бұрын
Thanks for this explanation! This was definitely an awkwardly worded problem.
@lovuitchen9332
@lovuitchen9332 3 жыл бұрын
Use "update" method of the set, one line less code of adding "t" back to the "nextDP" every inner loop :)
@NeetCode
@NeetCode 3 жыл бұрын
Good point!
@subramanisrinivasan6023
@subramanisrinivasan6023 3 жыл бұрын
Or you can use for t in set(dp): dp.add(t + num[i])
@devanshimittal7986
@devanshimittal7986 13 күн бұрын
Hey ! How can I develop coding intuition the way you have ?
@erlieshang5228
@erlieshang5228 3 жыл бұрын
all solutions you explained are O(N^2)??
@ruthviks
@ruthviks 11 ай бұрын
Hey, neetcode! Thanks for the walkthrough for this solution. It really was a interesting problem.
@danielsun716
@danielsun716 2 жыл бұрын
This is a 0/1 Knapsack problem. For your review of the certain pattern, I just edit them into 3 different ways that Neetcode teach me in Coin Change 2 step by step. I think even though the running time is not fast enough, but there are more intuitive. 1st, recursive DP, TO(mn), MO(mn) if sum(nums) % 2: return False target = sum(nums) / 2 dp = {} def dfs(i, a): if a == target: return True if a > target: return False if i == len(nums): return False if (i, a) in dp: return dp[(i, a)] dp[(i, a)] = dfs(i + 1, a + nums[i]) or dfs(i + 1, a) return dp[(i, a)] return dfs(0, 0) 2nd, 2D iterative DP, TO(mn), MO(mn) if sum(nums) % 2: return False # must be "//" because "/" operation is float object target = sum(nums) // 2 dp = [[False] * (len(nums) + 1) for i in range(target + 1)] dp[0] = [True] * (len(nums) + 1) for a in range(1, target + 1): for i in range(len(nums) - 1, -1, -1): if a < nums[i]: dp[a][i] = dp[a][i + 1] else: dp[a][i] = dp[a][i + 1] | dp[a - nums[i]][i + 1] return dp[target][0] 3rd, 1D iterative DP, TO(mn), MO(n) if sum(nums) % 2: return False target = sum(nums) // 2 dp = [False] * (target + 1) dp[0] = True for i in range(len(nums) - 1, -1, -1): nextDP = [False] * (target + 1) nextDP[0] = True for a in range(1, target + 1): nextDP[a] = dp[a] if a - nums[i] >= 0: nextDP[a] = dp[a] or dp[a - nums[i]] dp = nextDP return dp[target] I hope this gonna help you more to understand 0/1 or unbound knapsack problems patterns.
@zen5882
@zen5882 Жыл бұрын
thanks a lot
@Jambajakumba
@Jambajakumba Жыл бұрын
Awesome, thank you
@srinivasnimmala5608
@srinivasnimmala5608 Жыл бұрын
Thankyou. You explain things very clearly and provide simple solutions.
@AKSHAYMALU-oc1wp
@AKSHAYMALU-oc1wp 3 ай бұрын
I think i might have a better solution that has a time complexity of O(n* log(n)) and space complexity ofO(1) The solution goes as follows int target=0; for(int i=0;i=0;i--){ if(target-nums[i]>=0){ target-=nums[i]; } } if(target ==0) return true; else return false; Please lmk if this is a better approach or am i making a mistake somewhere!
@ilhamkabir1687
@ilhamkabir1687 Жыл бұрын
this is the best solution + explanation of this problem i've seen yet!! muchas gracias
@tannerhornsby2109
@tannerhornsby2109 Жыл бұрын
10:42 why isn't it O(2^n) where n is the length of the number array
@gordonlim2322
@gordonlim2322 2 жыл бұрын
Would have helped if you had code for the DFS solution. I didn't quite understand it.
@markolainovic
@markolainovic Жыл бұрын
I don't see why the time complexity for cached recursive solution is O(n*sum(nums)). The way I see it, for each index, we will have, at most, two items in the cache: (idx, target - nums[idx]) and (idx, target), So, the complexity should be O(2*n) => O(n) then?
@wussboi
@wussboi Ай бұрын
backtrack solution here in case anyone is interested: def canPartition(self, nums: List[int]) -> bool: target = sum(nums) / 2 def backtrack(i, total): # base case if total == target: return True if total > target or i == len(nums): return False # recursive case return backtrack(i + 1, total + nums[i]) or backtrack(i + 1, total) return backtrack(0, 0)
@princeofexcess
@princeofexcess 3 ай бұрын
Doesnt starting backwards and starting at index 0 yield the same results? am i missing something?
@JamesBond-mq7pd
@JamesBond-mq7pd 3 ай бұрын
yes. you will get same results. also you can exit if you found target
@TuanNguyen-to7nr
@TuanNguyen-to7nr 3 жыл бұрын
i think we shouldn't add to the set if (t + nums[i]) > target because the arr containing only positive numbers
@NeetCode
@NeetCode 3 жыл бұрын
Yes that's true, that's good way to speed it up
@sheltonsong6120
@sheltonsong6120 2 жыл бұрын
@@NeetCode Also the time complexity is O(n^2), obviously you have two nested for loops here.
@cout...codingandstuff
@cout...codingandstuff 3 ай бұрын
Bro by just adding a 0 in your next dp when i == 0, you can skip the whole newDp.add(t) part for the rest of iterations, cause adding 't' to 0 is always gonna give you the 't' itself
@aliakbar1062
@aliakbar1062 2 жыл бұрын
One and the only one well explained video
@orangethemeow
@orangethemeow 2 жыл бұрын
Can we check if the target is in dp before going through all elements in nums?
@prasad9012
@prasad9012 2 жыл бұрын
Could someone explain how is the time complexity of the final solution O(n * sums(nums))?
@송둡
@송둡 2 жыл бұрын
The outer for loop iterates n times, and in the inner for loop we are iterating size(dp), which upper bound is sum(nums) since dp basically stores the possible sums of a subset
@mavaamusicmachine2241
@mavaamusicmachine2241 2 жыл бұрын
@@송둡 Thank you for your explanation!
@vijayakumareyunni6010
@vijayakumareyunni6010 9 ай бұрын
"I loop backwards as I am used to it" -- not a good explanation and it's a red flag in interviews.
@OwenWu-f9t
@OwenWu-f9t 8 ай бұрын
exactly - it seems like he's just memorizing code at this point
@YING-JIEHXIA
@YING-JIEHXIA 6 ай бұрын
Can cast the set to a list `list(dp)` while looping through it
@algorithmo134
@algorithmo134 3 жыл бұрын
@Neetcode Can you do this next! 1031. Maximum Sum of Two Non-Overlapping Subarrays
@shardx191
@shardx191 3 жыл бұрын
what if we want to make n partitions, not just 2, is there's a way to do this using DP?
@colin398
@colin398 2 жыл бұрын
This is the greatest combination sum of all time
@JamesBond-mq7pd
@JamesBond-mq7pd 3 ай бұрын
For anyone wondering this is DFS Solution with memoization . Passes all tests but LC says Memory Limit Exceeded class Solution: def canPartition(self, nums: List[int]) -> bool: if sum(nums) % 2: return False hashmap = {} def dfs(target: int, i: int) -> bool: if (target, i) in hashmap: return hashmap[(target, i)] if target == 0: return True if len(nums) == i or target < 0: return False left = dfs(target - nums[i], i + 1) right = dfs(target, i + 1) hashmap[(target, i)] = left or right return hashmap[(target, i)] return dfs(sum(nums) // 2, 0)
@pomsky-spirit
@pomsky-spirit 2 жыл бұрын
Awesome ! what if I need to print the resulting arrays?
@ferb7o2
@ferb7o2 Жыл бұрын
I think that'd make it a HARD problem
@hector8733
@hector8733 2 жыл бұрын
Can some please explain why its O(n*sum(nums)/2) and not just O(n*m)? In order words how do we know that the number of sums in dp will be equal to target?
@radishanim
@radishanim Жыл бұрын
When you say "shouldn't it be O(n*m)", what is m?
@LeoLeung.93
@LeoLeung.93 2 жыл бұрын
very elegant solution, thanks so much
@akhma102
@akhma102 Ай бұрын
Brilliant! Thank you!
@minarefaat1573
@minarefaat1573 2 жыл бұрын
So we can solve 0/1 knapsack problem with the same technique??
@ahmedsafwat8331
@ahmedsafwat8331 3 жыл бұрын
Amazing explanation, I'm wondering if I can I sort the array and work with two pointers I will add a summation from both sides till I reach the limit which is the array sum/2. I'm not sure tho if this is good or not or if this will work or not
@WdnUlik2no
@WdnUlik2no 3 жыл бұрын
I thought about sorting and using two pointers at either end. But wasn’t sure it’ll work so I abandoned idea that idea.
@FlexGC
@FlexGC 2 жыл бұрын
@@WdnUlik2no how would your pointers work? You would also need more than two pointers as 1,5,5,11 would require 3 pointers lkj to calculate from the left side from a sorted array.
@joez5228
@joez5228 2 жыл бұрын
this will not work if the case is 1 1 2 2
@kross3359
@kross3359 2 жыл бұрын
@@joez5228 yeah thats correct. That will only work if average of all then numbers is present in the array and sum of all the elements is even.
@s750716
@s750716 2 жыл бұрын
nice solution and great explanation.
@OwenWu-f9t
@OwenWu-f9t 8 ай бұрын
you didn't explain why you are using a set and also why you are iterating over backwards as if I change your solution to iterating normally from left to right, it works too
@albertd7658
@albertd7658 Жыл бұрын
Faster than 95%. We don't need to create a new set while iterating and reassigning dp. Just taking a snapshot of the dp before the iteration will save quite a lot of time. Also checking if smaller than the target before adding is helpful for the space complexity as well. total = sum(nums) if total % 2: return False dp = set([0]) target = total // 2 for n in nums: for d in dp.copy(): tmp = n + d if tmp == target: return True if tmp < target: dp.add(tmp) return False
@sreenidhisreesha
@sreenidhisreesha Жыл бұрын
how? dp.copy() is creating a new set .
@Jambajakumba
@Jambajakumba Жыл бұрын
this fails [1,5,11,7]. Set this as return -> return True if d in dp else False
@Eeeason-c5y
@Eeeason-c5y 11 ай бұрын
snapshot is to create a new set...
@esprit-xd2lq
@esprit-xd2lq 4 ай бұрын
did you know that replacing `for i in range(len(nums)-1, -1, -1)` with `for i in range(len(nums))` will also work? don't really see what's so DP about this task. We essentially just go through array saving every possible sum at each point, and then return `return target in dp` and that's it. Brute-force af, no?
@ushasr2821
@ushasr2821 Ай бұрын
This solution is nothing but storing unique sum of all possible subsets right? just tried with this time complexity is really bad(639s it was), compared to memoization technique(64s).
@SomneelMaity
@SomneelMaity 2 жыл бұрын
This solution is amazing
@purnawirmanhuang5145
@purnawirmanhuang5145 Жыл бұрын
i think it's interesting you have tendency to count backward from length - 1 for DP problems. You almost apply backward counting even though this problem does not require backward counting with your formulation. I on the other hand, always try to count forward....., it makes learning your video extra effort to understand them 😅
@akashanand3783
@akashanand3783 3 жыл бұрын
Great Explanation 🙌
@xinniu3145
@xinniu3145 2 жыл бұрын
This is great! Thank you!
@MrOlu1234
@MrOlu1234 Жыл бұрын
He works so fast
@WdnUlik2no
@WdnUlik2no 3 жыл бұрын
Finally a clear explanation. Thanks! I don’t know Python but I should be able to apply this to Java.
@jonaskhanwald566
@jonaskhanwald566 3 жыл бұрын
Thanks for this. Expecting WORD BREAK soon
@NeetCode
@NeetCode 3 жыл бұрын
Sure I'll probably do it tomorrow or the day after
@hazmat5515
@hazmat5515 2 жыл бұрын
It seems that you don't need to traverse the array backwards and the algorithm still works.
@letscodebyaparna3698
@letscodebyaparna3698 Жыл бұрын
why is target considered as 11?
@nikhilgoyal007
@nikhilgoyal007 Жыл бұрын
this solution looks lie 2^n in time ? we are adding all possible subsets. Sure there can be repetition but we still will need be to iterate over all possibilities.
@rlavanya8447
@rlavanya8447 3 жыл бұрын
Thanks, waiting for Range module
@NeetCode
@NeetCode 3 жыл бұрын
Sure, I'll try to do it this week
@rajkane989
@rajkane989 Жыл бұрын
Another way to approach this problem is just the Target Sum problem with target = 0
@bojiang2869
@bojiang2869 2 жыл бұрын
Hi, I just have a question, I tried to create "nextDP=dp" in line 11 instead of creating an empty set. In that way, I can remove line 16 to add the original DP values back. But this method failed as the dp changed with iterations. I cannot understand why is that.
@joshuawilkinson3035
@joshuawilkinson3035 2 жыл бұрын
The reason is because nextDP=dp is setting it to an existing object, not copying its values. you can do nextDP = set(dp) or list(dp) to only copy the values
@truongkimson
@truongkimson 6 ай бұрын
Neetcode really gaslit me into thinking his solution is O(n*t) and not O(2^n) 😂
@sohambhattacharya767
@sohambhattacharya767 2 жыл бұрын
This solution gives a TLE in cpp.
@jaywalk17
@jaywalk17 2 жыл бұрын
last line could just be: return target in dp
@yassineacherkouk
@yassineacherkouk 11 ай бұрын
that's a tricky one.
@shoujojosei6705
@shoujojosei6705 2 жыл бұрын
Got youtube premium because of neetcode :))
@feDlugo
@feDlugo 3 жыл бұрын
Best solution!!!! You are a crack
@mashab9129
@mashab9129 3 жыл бұрын
brilliant!
@edwardteach2
@edwardteach2 3 жыл бұрын
U a God
@betafuchs8490
@betafuchs8490 Жыл бұрын
Implemted this solution in C++, get a time limit exceeded error
@luizfcavalcanti
@luizfcavalcanti Жыл бұрын
Hi! This is how I did it in JavaScript using the explanation in the video and some improvements discussed in the comments bellow: var canPartition = function(nums) { const total = nums.reduce((acum, curr) => acum + curr,0); if(total % 2) return false; const len = nums.length; const target = total / 2; let dp = new Set(); dp.add(0); for(let idx = 0; idx < len; idx++){ if(nums[idx] > target) return false; arrayDp = [...dp.values()]; for(let idxDp = 0; idxDp < arrayDp.length; idxDp++){ let currValue = arrayDp[idxDp] + nums[idx]; if(currValue == target) return true; if(currValue < target) dp.add(currValue); } } return false; }; It beats 85% in Runtime and 67.8% in memory.
@akhma102
@akhma102 Жыл бұрын
Wowow brother!
@mahmoudaboudeghedy6395
@mahmoudaboudeghedy6395 Жыл бұрын
perfect
@shaysarn2235
@shaysarn2235 3 ай бұрын
13:24
@sushantrocks
@sushantrocks 3 жыл бұрын
Very reminiscent of bfs
@CS_n00b
@CS_n00b Жыл бұрын
anyone have a memoization python solution?
@rapscalliondave
@rapscalliondave 4 ай бұрын
sorry, little late but hope this helps - target = sum(nums) if target % 2 != 0: return False target = target / 2 dp = {} def helper(i, s): if s == target: return True if s > target or i >= len(nums): return False if (i, s) in dp: return dp[(i, s)] dp[(i, s)] = helper(i + 1, s + nums[i]) or helper(i + 1, s) return dp[(i, s)] return helper(0, 0)
@chilly2171
@chilly2171 2 жыл бұрын
Your brute force approach seems wrong already, you return true when it is 11, but the other subset might not add up to 11. And why you decide to do it backwards?
@alexm1930
@alexm1930 2 жыл бұрын
Sum of total was 22 so half is exactly 11, therefore finding half with 11 will mean the remaining half is also 11. He started from the back because usually DP approaches are bottom up. He explains in the video that it doesn't matter if you start from front or back, but just did it because he's used to it.
@joez5228
@joez5228 2 жыл бұрын
@@alexm1930 Thanks for the explanation! I was confused too. Since 22 is the sum of the nums, if we can find the subarray that is equal to the target 11 then the sum of remaining nums always equal to the target 11.
@nikhil199029
@nikhil199029 2 жыл бұрын
Better approach: 1. Sort the array. 2. Save cumulative sum like cadanes algorithm. 3. Binary search for sum/2 value. If found return true
@findingMyself.25yearsago
@findingMyself.25yearsago 2 жыл бұрын
can you elaborate on this??
@temporarychannel4339
@temporarychannel4339 2 жыл бұрын
sort has a O(n^2) complexity + the added time complexity of step 2 and 3.
@erikshure360
@erikshure360 Жыл бұрын
@@temporarychannel4339 ... for an array n, sort takes O(n*log(n)) the other work is irrelevant as the dominant growth rate is n*log(n). That said, OP's solution is still dubious.
@temporarychannel4339
@temporarychannel4339 Жыл бұрын
@@erikshure360 that's true how silly of me, my answer was misleading, I'll edit it.
@nikhil199029
@nikhil199029 7 ай бұрын
@@temporarychannel4339 sorry I was wrong.
@Tt-wm1ze
@Tt-wm1ze 3 жыл бұрын
hi do you have an email adress
Making an Algorithm Faster
30:08
NeetCodeIO
Рет қаралды 120 М.
REAL 3D brush can draw grass Life Hack #shorts #lifehacks
00:42
MrMaximus
Рет қаралды 8 МЛН
Бенчик, пора купаться! 🛁 #бенчик #арти #симбочка
00:34
Симбочка Пимпочка
Рет қаралды 3 МЛН
How I would learn Leetcode if I could start over
18:03
NeetCodeIO
Рет қаралды 601 М.
10 Math Concepts for Programmers
9:32
Fireship
Рет қаралды 1,9 МЛН
5 Simple Steps for Solving Any Recursive Problem
21:03
Reducible
Рет қаралды 1,2 МЛН
Word Break - Dynamic Programming - Leetcode 139 - Python
15:35
DP 15. Partition Equal Subset Sum | DP on Subsequences
9:43
take U forward
Рет қаралды 213 М.
REAL 3D brush can draw grass Life Hack #shorts #lifehacks
00:42
MrMaximus
Рет қаралды 8 МЛН