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.
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
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
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.
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])
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.
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
@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)
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.
@@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)
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
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.
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]
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....
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.
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)
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.
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.
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..
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.
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?
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]
@@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)?
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) ?
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)
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
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
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 :)
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)
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
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!
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?
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
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?
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 😅
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 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.
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
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
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).
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?
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.
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.
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.
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
@@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.
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)
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?
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.
@@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.
![[DRIP] ‘CLIK CLAK’ PREVIEW](http://i.ytimg.com/vi/bcxkcOSbpac/mqdefault.jpg)
💡 DP Playlist: th-cam.com/video/73r3KWiEvyk/w-d-xo.html
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.
Same. Makes so much sense.
My god, sometimes I am so dumb
Thank you for this comment
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
My thinking exactly, I was puzzled by the fact that he iterated backwards
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
he said you can do it in forward order, he just likes it backward
@@mahmoudalsayed1138 if you have watched his video, he loves backwards for no reason
This solution was the best from what I've seen so far: fast, short and well explained.
We can check if (t + nums[I]
Honestly how the hell is someone supposed to come up with such a solution in half an hour during an interview?
Exactly, like what the hell are people on any new drug
It's these irritations of life that fuel my existentialism.
Easy, know the solution already and pretend it's your first time seeing it. Just like most of these bs questions lol
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
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.
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])
Perfect! I also thought DP might be a bit of a confusing name for a set.
Subsums definitely makes more sense.
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.
This was by far the best code that I could actually mentally follow along with and not be totally lost in the middle.
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.
This is exactly what I thought
This was a clever approach. Simpler than using a 2d array -- as do most tutorials on TH-cam
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
why you in reverse way? just does not make sense it works in both way
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.
Why is the memory complexity not O(2^n)? we are in practice finding every subset and checking the sum?
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
@@sonnguyen8819 oh yes you’re correct thanks
by far the best explanation I've found, thank you so much for posting this and doing a great job explaining all the steps.
@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)
Yes.. the "optimal solution" is literally brute force... bruh.
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.
@@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)
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
You really like to start from the end and go backwards! literally zero reasons to do that here :D
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.
thanks a lot
Awesome, thank you
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]
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....
@@markolainovic Yes because it is finding out the sum/ possibility to exist the target from each no which ultimately useful to build the table.
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.
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)
time complexity appears to be 2^N, since all the values are generated and stored - a loop for every value
you can use dp |= nextDP the set union instead of dp = nextDP to avoid nextDP.add(t)
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.
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.
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..
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.
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.
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?
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]
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).
I figure it out... total number of sums in the hashset will be
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
The time complex of last solution is 2 ^ (n+1) (1 + 2 + 4 + 8..... 2 ^n) ---> G.P , but space is O ( target)
@@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)?
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) ?
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)
Thanks a lot, can you tell me how do you convert a decision tree into recursion?
Use "update" method of the set, one line less code of adding "t" back to the "nextDP" every inner loop :)
Good point!
Or you can use for t in set(dp): dp.add(t + num[i])
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
Brother, your videos have been of great help! It's the best explanation I've seen so far
all solutions you explained are O（N^2)??
i think we shouldn't add to the set if (t + nums[i]) > target because the arr containing only positive numbers
Yes that's true, that's good way to speed it up
@@NeetCode Also the time complexity is O(n^2), obviously you have two nested for loops here.
Why would you iterate backwards?
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?
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
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 :)
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)
@Neetcode Can you do this next! 1031. Maximum Sum of Two Non-Overlapping Subarrays
Thanks for this explanation! This was definitely an awkwardly worded problem.
this is the best solution + explanation of this problem i've seen yet!! muchas gracias
Thankyou. You explain things very clearly and provide simple solutions.
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)?
Hey, neetcode! Thanks for the walkthrough for this solution. It really was a interesting problem.
One and the only one well explained video
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
how? dp.copy() is creating a new set .
this fails [1,5,11,7]. Set this as return -> return True if d in dp else False
snapshot is to create a new set...
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!
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?
Would have helped if you had code for the DFS solution. I didn't quite understand it.
10:42 why isn't it O(2^n) where n is the length of the number array
Awesome ! what if I need to print the resulting arrays?
I think that'd make it a HARD problem
Could someone explain how is the time complexity of the final solution O(n * sums(nums))?
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
@@송둡 Thank you for your explanation!
Can we check if the target is in dp before going through all elements in nums?
Brilliant! Thank you!
Hey ! How can I develop coding intuition the way you have ?
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?
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 😅
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
I thought about sorting and using two pointers at either end. But wasn’t sure it’ll work so I abandoned idea that idea.
@@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.
this will not work if the case is 1 1 2 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.
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
This is the greatest combination sum of all time
nice solution and great explanation.
very elegant solution, thanks so much
So we can solve 0/1 knapsack problem with the same technique??
Can cast the set to a list `list(dp)` while looping through it
what if we want to make n partitions, not just 2, is there's a way to do this using DP?
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
Great Explanation 🙌
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).
This is great! Thank you!
"I loop backwards as I am used to it" -- not a good explanation and it's a red flag in interviews.
exactly - it seems like he's just memorizing code at this point
It seems that you don't need to traverse the array backwards and the algorithm still works.
Doesnt starting backwards and starting at index 0 yield the same results? am i missing something?
yes. you will get same results. also you can exit if you found target
Finally a clear explanation. Thanks! I don’t know Python but I should be able to apply this to Java.
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?
When you say "shouldn't it be O(n*m)", what is m?
This solution is amazing
Thanks for this. Expecting WORD BREAK soon
Sure I'll probably do it tomorrow or the day after
Another way to approach this problem is just the Target Sum problem with target = 0
Neetcode really gaslit me into thinking his solution is O(n*t) and not O(2^n) 😂
He works so fast
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.
why is target considered as 11?
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.
Thanks, waiting for Range module
Sure, I'll try to do it this week
last line could just be:
return target in dp
This solution gives a TLE in cpp.
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.
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
Wowow brother!
brilliant!
Best solution!!!! You are a crack
Got youtube premium because of neetcode :))
Better approach:
1. Sort the array.
2. Save cumulative sum like cadanes algorithm.
3. Binary search for sum/2 value. If found return true
can you elaborate on this??
sort has a O(n^2) complexity + the added time complexity of step 2 and 3.
@@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.
@@erikshure360 that's true how silly of me, my answer was misleading, I'll edit it.
@@temporarychannel4339 sorry I was wrong.
Implemted this solution in C++, get a time limit exceeded error
U a God
perfect
that's a tricky one.
13:24
Very reminiscent of bfs
anyone have a memoization python solution?
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)
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?
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.
@@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.
hi do you have an email adress