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 Жыл бұрын
Same. Makes so much sense.
@falcomomo Жыл бұрын
My god, sometimes I am so dumb
@ivivivivvivivivivivivivАй бұрын
Thank you for this comment
@minciNashu2 жыл бұрын
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 Жыл бұрын
My thinking exactly, I was puzzled by the fact that he iterated backwards
@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
@truongkimson6 ай бұрын
he said you can do it in forward order, he just likes it backward
@ziyuzhao24428 күн бұрын
@@mahmoudalsayed1138 if you have watched his video, he loves backwards for no reason
@msh104utube3 жыл бұрын
This solution was the best from what I've seen so far: fast, short and well explained.
@AnikaRathi92 жыл бұрын
We can check if (t + nums[I]
@mohammadhoseinabbasi99932 жыл бұрын
Honestly how the hell is someone supposed to come up with such a solution in half an hour during an interview?
@adityabohra69915 ай бұрын
Exactly, like what the hell are people on any new drug
@fabricator.cap.hill.seattle5 ай бұрын
It's these irritations of life that fuel my existentialism.
@EE123454 ай бұрын
Easy, know the solution already and pretend it's your first time seeing it. Just like most of these bs questions lol
@dingus23323 ай бұрын
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...codingandstuff3 ай бұрын
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.
@siqb3 жыл бұрын
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])
@CostaKazistov2 жыл бұрын
Perfect! I also thought DP might be a bit of a confusing name for a set. Subsums definitely makes more sense.
@navaneethmkrishnan63742 жыл бұрын
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.
@SmoothCode2 жыл бұрын
This was by far the best code that I could actually mentally follow along with and not be totally lost in the middle.
@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 Жыл бұрын
This is exactly what I thought
@Dhruvbala3 ай бұрын
This was a clever approach. Simpler than using a 2d array -- as do most tutorials on KZbin
@ruthviks11 ай бұрын
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
@cleancodeET5 ай бұрын
why you in reverse way? just does not make sense it works in both way
@restindev3 жыл бұрын
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.
@zzzzzzzjsjyue21759 ай бұрын
Why is the memory complexity not O(2^n)? we are in practice finding every subset and checking the sum?
@sonnguyen88196 ай бұрын
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
@zzzzzzzjsjyue21756 ай бұрын
@@sonnguyen8819 oh yes you’re correct thanks
@andrepinto78952 жыл бұрын
You really like to start from the end and go backwards! literally zero reasons to do that here :D
@alirezaaghamohammadi29553 жыл бұрын
by far the best explanation I've found, thank you so much for posting this and doing a great job explaining all the steps.
@juliramoos8 ай бұрын
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?
@truongkimson6 ай бұрын
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]
@ismailkaracakaya2602 жыл бұрын
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 Жыл бұрын
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....
@tusharmore38602 ай бұрын
@@markolainovic Yes because it is finding out the sum/ possibility to exist the target from each no which ultimately useful to build the table.
@swapnilsdt2 жыл бұрын
@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 Жыл бұрын
Yes.. the "optimal solution" is literally brute force... bruh.
@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 Жыл бұрын
@@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)
@truongkimson6 ай бұрын
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
@spano17239 ай бұрын
Why would you iterate backwards?
@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Күн бұрын
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) ?
@jing69342 жыл бұрын
you can use dp |= nextDP the set union instead of dp = nextDP to avoid nextDP.add(t)
@ax53443 жыл бұрын
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.
@NeetCode3 жыл бұрын
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 Жыл бұрын
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 Жыл бұрын
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)
@vishweshganapathy818911 ай бұрын
time complexity appears to be 2^N, since all the values are generated and stored - a loop for every value
@Kaushikraj98452 жыл бұрын
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 Жыл бұрын
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.
@kaci02363 ай бұрын
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)?
@obitonamizake45392 жыл бұрын
Thanks a lot, can you tell me how do you convert a decision tree into recursion?
@JefferyChiang-l3x2 жыл бұрын
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-l3x2 жыл бұрын
I figure it out... total number of sums in the hashset will be
@feeltheheat962 жыл бұрын
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-zs2sv2 жыл бұрын
The time complex of last solution is 2 ^ (n+1) (1 + 2 + 4 + 8..... 2 ^n) ---> G.P , but space is O ( target)
@pepehimovic31352 жыл бұрын
@@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)?
@utsavmathur14783 жыл бұрын
Brother, your videos have been of great help! It's the best explanation I've seen so far
@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
@berkeevrensevdi17882 жыл бұрын
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-lz1pg2 жыл бұрын
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
@berkeevrensevdi17882 жыл бұрын
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 Жыл бұрын
Thanks for this explanation! This was definitely an awkwardly worded problem.
@lovuitchen93323 жыл бұрын
Use "update" method of the set, one line less code of adding "t" back to the "nextDP" every inner loop :)
@NeetCode3 жыл бұрын
Good point!
@subramanisrinivasan60233 жыл бұрын
Or you can use for t in set(dp): dp.add(t + num[i])
@devanshimittal798613 күн бұрын
Hey ! How can I develop coding intuition the way you have ?
@erlieshang52283 жыл бұрын
all solutions you explained are O(N^2)??
@ruthviks11 ай бұрын
Hey, neetcode! Thanks for the walkthrough for this solution. It really was a interesting problem.
@danielsun7162 жыл бұрын
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 Жыл бұрын
thanks a lot
@Jambajakumba Жыл бұрын
Awesome, thank you
@srinivasnimmala5608 Жыл бұрын
Thankyou. You explain things very clearly and provide simple solutions.
@AKSHAYMALU-oc1wp3 ай бұрын
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 Жыл бұрын
this is the best solution + explanation of this problem i've seen yet!! muchas gracias
@tannerhornsby2109 Жыл бұрын
10:42 why isn't it O(2^n) where n is the length of the number array
@gordonlim23222 жыл бұрын
Would have helped if you had code for the DFS solution. I didn't quite understand it.
@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Ай бұрын
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)
@princeofexcess3 ай бұрын
Doesnt starting backwards and starting at index 0 yield the same results? am i missing something?
@JamesBond-mq7pd3 ай бұрын
yes. you will get same results. also you can exit if you found target
@TuanNguyen-to7nr3 жыл бұрын
i think we shouldn't add to the set if (t + nums[i]) > target because the arr containing only positive numbers
@NeetCode3 жыл бұрын
Yes that's true, that's good way to speed it up
@sheltonsong61202 жыл бұрын
@@NeetCode Also the time complexity is O(n^2), obviously you have two nested for loops here.
@cout...codingandstuff3 ай бұрын
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
@aliakbar10622 жыл бұрын
One and the only one well explained video
@orangethemeow2 жыл бұрын
Can we check if the target is in dp before going through all elements in nums?
@prasad90122 жыл бұрын
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
@mavaamusicmachine22412 жыл бұрын
@@송둡 Thank you for your explanation!
@vijayakumareyunni60109 ай бұрын
"I loop backwards as I am used to it" -- not a good explanation and it's a red flag in interviews.
@OwenWu-f9t8 ай бұрын
exactly - it seems like he's just memorizing code at this point
@YING-JIEHXIA6 ай бұрын
Can cast the set to a list `list(dp)` while looping through it
@algorithmo1343 жыл бұрын
@Neetcode Can you do this next! 1031. Maximum Sum of Two Non-Overlapping Subarrays
@shardx1913 жыл бұрын
what if we want to make n partitions, not just 2, is there's a way to do this using DP?
@colin3982 жыл бұрын
This is the greatest combination sum of all time
@JamesBond-mq7pd3 ай бұрын
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-spirit2 жыл бұрын
Awesome ! what if I need to print the resulting arrays?
@ferb7o2 Жыл бұрын
I think that'd make it a HARD problem
@hector87332 жыл бұрын
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 Жыл бұрын
When you say "shouldn't it be O(n*m)", what is m?
@LeoLeung.932 жыл бұрын
very elegant solution, thanks so much
@akhma102Ай бұрын
Brilliant! Thank you!
@minarefaat15732 жыл бұрын
So we can solve 0/1 knapsack problem with the same technique??
@ahmedsafwat83313 жыл бұрын
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
@WdnUlik2no3 жыл бұрын
I thought about sorting and using two pointers at either end. But wasn’t sure it’ll work so I abandoned idea that idea.
@FlexGC2 жыл бұрын
@@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.
@joez52282 жыл бұрын
this will not work if the case is 1 1 2 2
@kross33592 жыл бұрын
@@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.
@s7507162 жыл бұрын
nice solution and great explanation.
@OwenWu-f9t8 ай бұрын
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 Жыл бұрын
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 Жыл бұрын
how? dp.copy() is creating a new set .
@Jambajakumba Жыл бұрын
this fails [1,5,11,7]. Set this as return -> return True if d in dp else False
@Eeeason-c5y11 ай бұрын
snapshot is to create a new set...
@esprit-xd2lq4 ай бұрын
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Ай бұрын
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).
@SomneelMaity2 жыл бұрын
This solution is amazing
@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 😅
@akashanand37833 жыл бұрын
Great Explanation 🙌
@xinniu31452 жыл бұрын
This is great! Thank you!
@MrOlu1234 Жыл бұрын
He works so fast
@WdnUlik2no3 жыл бұрын
Finally a clear explanation. Thanks! I don’t know Python but I should be able to apply this to Java.
@jonaskhanwald5663 жыл бұрын
Thanks for this. Expecting WORD BREAK soon
@NeetCode3 жыл бұрын
Sure I'll probably do it tomorrow or the day after
@hazmat55152 жыл бұрын
It seems that you don't need to traverse the array backwards and the algorithm still works.
@letscodebyaparna3698 Жыл бұрын
why is target considered as 11?
@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.
@rlavanya84473 жыл бұрын
Thanks, waiting for Range module
@NeetCode3 жыл бұрын
Sure, I'll try to do it this week
@rajkane989 Жыл бұрын
Another way to approach this problem is just the Target Sum problem with target = 0
@bojiang28692 жыл бұрын
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.
@joshuawilkinson30352 жыл бұрын
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
@truongkimson6 ай бұрын
Neetcode really gaslit me into thinking his solution is O(n*t) and not O(2^n) 😂
@sohambhattacharya7672 жыл бұрын
This solution gives a TLE in cpp.
@jaywalk172 жыл бұрын
last line could just be: return target in dp
@yassineacherkouk11 ай бұрын
that's a tricky one.
@shoujojosei67052 жыл бұрын
Got youtube premium because of neetcode :))
@feDlugo3 жыл бұрын
Best solution!!!! You are a crack
@mashab91293 жыл бұрын
brilliant!
@edwardteach23 жыл бұрын
U a God
@betafuchs8490 Жыл бұрын
Implemted this solution in C++, get a time limit exceeded error
@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 Жыл бұрын
Wowow brother!
@mahmoudaboudeghedy6395 Жыл бұрын
perfect
@shaysarn22353 ай бұрын
13:24
@sushantrocks3 жыл бұрын
Very reminiscent of bfs
@CS_n00b Жыл бұрын
anyone have a memoization python solution?
@rapscalliondave4 ай бұрын
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)
@chilly21712 жыл бұрын
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?
@alexm19302 жыл бұрын
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.
@joez52282 жыл бұрын
@@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.
@nikhil1990292 жыл бұрын
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.25yearsago2 жыл бұрын
can you elaborate on this??
@temporarychannel43392 жыл бұрын
sort has a O(n^2) complexity + the added time complexity of step 2 and 3.
@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 Жыл бұрын
@@erikshure360 that's true how silly of me, my answer was misleading, I'll edit it.