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

Поделиться
HTML-код
  • Опубликовано: 9 янв 2025

Комментарии • 179

  • @NeetCode
    @NeetCode  3 года назад +14

    💡 DP Playlist: ruclips.net/video/73r3KWiEvyk/видео.html

  • @mr6462
    @mr6462 2 года назад +129

    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.

  • @minciNashu
    @minciNashu 2 года назад +67

    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 Год назад +12

      My thinking exactly, I was puzzled by the fact that he iterated backwards

    • @strawberriesandcream2863
      @strawberriesandcream2863 Год назад +8

      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 9 месяцев назад +1

      he said you can do it in forward order, he just likes it backward

    • @ziyuzhao2442
      @ziyuzhao2442 3 месяца назад

      @@mahmoudalsayed1138 if you have watched his video, he loves backwards for no reason

  • @msh104utube
    @msh104utube 3 года назад +40

    This solution was the best from what I've seen so far: fast, short and well explained.

  • @mohammadhoseinabbasi9993
    @mohammadhoseinabbasi9993 2 года назад +77

    Honestly how the hell is someone supposed to come up with such a solution in half an hour during an interview?

    • @adityabohra6991
      @adityabohra6991 8 месяцев назад +6

      Exactly, like what the hell are people on any new drug

    • @fabricator.cap.hill.seattle
      @fabricator.cap.hill.seattle 8 месяцев назад +8

      It's these irritations of life that fuel my existentialism.

    • @EE12345
      @EE12345 7 месяцев назад +44

      Easy, know the solution already and pretend it's your first time seeing it. Just like most of these bs questions lol

    • @dingus2332
      @dingus2332 5 месяцев назад +1

      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 5 месяцев назад +2

      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.

  • @AnikaRathi9
    @AnikaRathi9 2 года назад +22

    We can check if (t + nums[I]

  • @SmoothCode
    @SmoothCode 2 года назад +7

    This was by far the best code that I could actually mentally follow along with and not be totally lost in the middle.

  • @siqb
    @siqb 3 года назад +30

    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 года назад +1

      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.

  • @kbirdx
    @kbirdx 4 месяца назад +5

    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)

  • @Darkmatterkun
    @Darkmatterkun Год назад +11

    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.

  • @Dhruvbala
    @Dhruvbala 6 месяцев назад +3

    This was a clever approach. Simpler than using a 2d array -- as do most tutorials on RUclips

  • @ruthviks
    @ruthviks Год назад +2

    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 8 месяцев назад

      why you in reverse way? just does not make sense it works in both way

  • @alirezaaghamohammadi2955
    @alirezaaghamohammadi2955 3 года назад +5

    by far the best explanation I've found, thank you so much for posting this and doing a great job explaining all the steps.

  • @restindev
    @restindev 3 года назад +9

    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.

  • @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.

  • @sentinel-y8l
    @sentinel-y8l 2 года назад +4

    You really like to start from the end and go backwards! literally zero reasons to do that here :D

  • @juliramoos
    @juliramoos 10 месяцев назад +2

    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 9 месяцев назад +2

      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]

  • @utsavmathur1478
    @utsavmathur1478 3 года назад +2

    Brother, your videos have been of great help! It's the best explanation I've seen so far

  • @zzzzzzzjsjyue2175
    @zzzzzzzjsjyue2175 Год назад +4

    Why is the memory complexity not O(2^n)? we are in practice finding every subset and checking the sum?

    • @sonnguyen8819
      @sonnguyen8819 9 месяцев назад

      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 9 месяцев назад

      @@sonnguyen8819 oh yes you’re correct thanks

    • @ashkan.arabim
      @ashkan.arabim 2 месяца назад

      ​@@sonnguyen8819 I really don't see how sum(nums) is better than 2^n. 2^n is all the subset sums, sum(nums) is even worse cuz if you have an array of [1, 1000] 2^n tells you that you'll use 4 units of space (which is correct) but sum(nums) will tell you you're using 1001 units of space.
      it's O(2^n). sorry mate.

  • @dheepthaaanand3214
    @dheepthaaanand3214 2 месяца назад +2

    Space complexity is restricted to O(sum(nums)) only if we add items to set

    • @milandoslic2121
      @milandoslic2121 Месяц назад

      It seems like it can be the case, but do you have some explanation on why in that case it is limited to n?

  • @JohnIdlewood
    @JohnIdlewood 19 дней назад

    1. it's also important to mention that sum doesn't overflow int32 within the given constraints, otherwise - it would be very fun
    2. How to intuitively come up with this solution. You'll have a lot of duplicate partial sum values that you can cache. Also take into account constraints. Because if nums[i] ~ 2^n, it'll still be better to use brute force solution - same time complexity, but less memory.
    3. Doesn't matter from which side of array to start.
    4. You don't need to store sums greater than target if nums[i] >= 0

  • @swapnilsdt
    @swapnilsdt 2 года назад +5

    @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 2 года назад +1

      Yes.. the "optimal solution" is literally brute force... bruh.

    • @DavidDLee
      @DavidDLee Год назад +3

      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 Год назад +1

      @@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 9 месяцев назад

      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

  • @DavidDLee
    @DavidDLee Год назад +1

    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 Год назад

      time complexity appears to be 2^N, since all the values are generated and stored - a loop for every value

  • @ilhamkabir1687
    @ilhamkabir1687 2 года назад

    this is the best solution + explanation of this problem i've seen yet!! muchas gracias

  • @tannerhornsby2109
    @tannerhornsby2109 Год назад +1

    10:42 why isn't it O(2^n) where n is the length of the number array

  • @fadsa342
    @fadsa342 Год назад

    Thanks for this explanation! This was definitely an awkwardly worded problem.

  • @ruthviks
    @ruthviks Год назад

    Hey, neetcode! Thanks for the walkthrough for this solution. It really was a interesting problem.

  • @jing6934
    @jing6934 2 года назад +1

    you can use dp |= nextDP the set union instead of dp = nextDP to avoid nextDP.add(t)

  • @aliakbar1062
    @aliakbar1062 3 года назад +1

    One and the only one well explained video

  • @ismailkaracakaya260
    @ismailkaracakaya260 2 года назад +5

    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 2 года назад

      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 4 месяца назад

      @@markolainovic Yes because it is finding out the sum/ possibility to exist the target from each no which ultimately useful to build the table.

  • @obitonamizake4539
    @obitonamizake4539 3 года назад +3

    Thanks a lot, can you tell me how do you convert a decision tree into recursion?

  • @srinivasnimmala5608
    @srinivasnimmala5608 2 года назад

    Thankyou. You explain things very clearly and provide simple solutions.

  • @danielsun716
    @danielsun716 2 года назад +5

    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.

  • @colin398
    @colin398 2 года назад

    This is the greatest combination sum of all time

  • @ax5344
    @ax5344 3 года назад +4

    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 года назад +4

      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.

  • @Kaushikraj9845
    @Kaushikraj9845 2 года назад +1

    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.

  • @lovuitchen9332
    @lovuitchen9332 3 года назад +2

    Use "update" method of the set, one line less code of adding "t" back to the "nextDP" every inner loop :)

  • @devanshimittal7986
    @devanshimittal7986 3 месяца назад +1

    Hey ! How can I develop coding intuition the way you have ?

  • @berkeevrensevdi1788
    @berkeevrensevdi1788 2 года назад +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 года назад +1

      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 года назад +1

      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 :)

  • @spano1723
    @spano1723 11 месяцев назад +1

    Why would you iterate backwards?

  • @JefferyChiang-l3x
    @JefferyChiang-l3x 3 года назад +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 3 года назад +3

      I figure it out... total number of sums in the hashset will be

    • @feeltheheat96
      @feeltheheat96 3 года назад +3

      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)?

  • @LeoLeung.93
    @LeoLeung.93 2 года назад

    very elegant solution, thanks so much

  • @prasad9012
    @prasad9012 2 года назад +2

    Could someone explain how is the time complexity of the final solution O(n * sums(nums))?

    • @송둡
      @송둡 2 года назад +4

      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!

  • @JamesBond-mq7pd
    @JamesBond-mq7pd 6 месяцев назад

    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)

  • @TuanNguyen-to7nr
    @TuanNguyen-to7nr 3 года назад +2

    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.

  • @anirudhhosur3827
    @anirudhhosur3827 Месяц назад

    Another day doing neetcode. Another day of depression! Why cant FAANG act like any other company and just ask what projects you have developed? No, they want to ask these crazy hard questions. Someone please send positive vibes. I feel like punching my laptop.

  • @s750716
    @s750716 3 года назад +1

    nice solution and great explanation.

  • @akashanand3783
    @akashanand3783 3 года назад +1

    Great Explanation 🙌

  • @erlieshang5228
    @erlieshang5228 3 года назад +7

    all solutions you explained are O(N^2)??

  • @gordonlim2322
    @gordonlim2322 2 года назад +1

    Would have helped if you had code for the DFS solution. I didn't quite understand it.

  • @orangethemeow
    @orangethemeow 2 года назад

    Can we check if the target is in dp before going through all elements in nums?

  • @kaci0236
    @kaci0236 6 месяцев назад

    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)?

  • @cout...codingandstuff
    @cout...codingandstuff 5 месяцев назад +1

    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

  • @RachelDong-y4s
    @RachelDong-y4s 2 месяца назад

    there are some improvements: if t is bigger than the target, then no need to store in set

  • @xinniu3145
    @xinniu3145 3 года назад +1

    This is great! Thank you!

  • @albertd7658
    @albertd7658 Год назад +2

    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 Год назад +1

      snapshot is to create a new set...

  • @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

  • @akhma102
    @akhma102 4 месяца назад

    Brilliant! Thank you!

  • @pomsky-spirit
    @pomsky-spirit 2 года назад +1

    Awesome ! what if I need to print the resulting arrays?

    • @ferb7o2
      @ferb7o2 2 года назад

      I think that'd make it a HARD problem

  • @susantamohapatra2973
    @susantamohapatra2973 2 месяца назад

    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) ?

  • @YING-JIEHXIA
    @YING-JIEHXIA 8 месяцев назад

    Can cast the set to a list `list(dp)` while looping through it

  • @WdnUlik2no
    @WdnUlik2no 3 года назад

    Finally a clear explanation. Thanks! I don’t know Python but I should be able to apply this to Java.

  • @SomneelMaity
    @SomneelMaity 2 года назад

    This solution is amazing

  • @ahmedsafwat8331
    @ahmedsafwat8331 3 года назад +1

    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 3 года назад

      @@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 3 года назад +2

      this will not work if the case is 1 1 2 2

    • @kross-1994
      @kross-1994 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.

  • @shardx191
    @shardx191 3 года назад

    what if we want to make n partitions, not just 2, is there's a way to do this using DP?

  • @algorithmo134
    @algorithmo134 3 года назад +1

    @Neetcode Can you do this next! 1031. Maximum Sum of Two Non-Overlapping Subarrays

  • @jonaskhanwald566
    @jonaskhanwald566 3 года назад

    Thanks for this. Expecting WORD BREAK soon

    • @NeetCode
      @NeetCode  3 года назад +2

      Sure I'll probably do it tomorrow or the day after

  • @markolainovic
    @markolainovic 2 года назад

    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?

  • @milandoslic2121
    @milandoslic2121 Месяц назад

    The space and time complexity is not correct.
    It seems like the length of the output set can grow by factor of 2 in every iteration if we get a new value every time. This means that in the worst case space is going to be (2^n) and time: (n * 2^n).

  • @vijayakumareyunni6010
    @vijayakumareyunni6010 Год назад +3

    "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 11 месяцев назад +1

      exactly - it seems like he's just memorizing code at this point

  • @samarthjain5015
    @samarthjain5015 7 дней назад

    This could also have been done straight instead of reverse.
    for num in nums:
    instead of
    for i in range(len(nums) - 1, -1, -1):

  • @AKSHAYMALU-oc1wp
    @AKSHAYMALU-oc1wp 5 месяцев назад

    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!

  • @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 2 года назад

      When you say "shouldn't it be O(n*m)", what is m?

  • @princeofexcess
    @princeofexcess 6 месяцев назад

    Doesnt starting backwards and starting at index 0 yield the same results? am i missing something?

    • @JamesBond-mq7pd
      @JamesBond-mq7pd 6 месяцев назад

      yes. you will get same results. also you can exit if you found target

  • @MrOlu1234
    @MrOlu1234 Год назад

    He works so fast

  • @rajkane989
    @rajkane989 2 года назад

    Another way to approach this problem is just the Target Sum problem with target = 0

  • @esprit-xd2lq
    @esprit-xd2lq 7 месяцев назад

    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?

  • @hazmat5515
    @hazmat5515 2 года назад

    It seems that you don't need to traverse the array backwards and the algorithm still works.

  • @minarefaat1573
    @minarefaat1573 3 года назад

    So we can solve 0/1 knapsack problem with the same technique??

  • @MrKondie
    @MrKondie Месяц назад

    I like how you acknowledge that the best way to come to the final solution is to first do the brute force recursive, memoize it, and then go for the optimized solution... but you totally skipped over the middle step. Classic neetcode...

  • @imerence6290
    @imerence6290 3 дня назад +1

    Would have bee much better if you showed 2D to 1D DP.

  • @rlavanya8447
    @rlavanya8447 3 года назад

    Thanks, waiting for Range module

    • @NeetCode
      @NeetCode  3 года назад +1

      Sure, I'll try to do it this week

  • @OwenWu-f9t
    @OwenWu-f9t 11 месяцев назад

    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

  • @shoujojosei6705
    @shoujojosei6705 2 года назад

    Got youtube premium because of neetcode :))

  • @jaywalk17
    @jaywalk17 2 года назад

    last line could just be:
    return target in dp

  • @sohambhattacharya767
    @sohambhattacharya767 2 года назад +1

    This solution gives a TLE in cpp.

  • @truongkimson
    @truongkimson 9 месяцев назад

    Neetcode really gaslit me into thinking his solution is O(n*t) and not O(2^n) 😂

  • @shaysarn2235
    @shaysarn2235 6 месяцев назад

    13:24

  • @letscodebyaparna3698
    @letscodebyaparna3698 Год назад

    why is target considered as 11?

  • @ushasr2821
    @ushasr2821 4 месяца назад

    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).

  • @purnawirmanhuang5145
    @purnawirmanhuang5145 Год назад +1

    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 😅

  • @bojiang2869
    @bojiang2869 3 года назад

    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 3 года назад +1

      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

  • @feDlugo
    @feDlugo 3 года назад

    Best solution!!!! You are a crack

  • @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.

  • @yassineacherkouk
    @yassineacherkouk Год назад

    that's a tricky one.

  • @mashab9129
    @mashab9129 3 года назад

    brilliant!

  • @edwardteach2
    @edwardteach2 3 года назад

    U a God

  • @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.

  • @betafuchs8490
    @betafuchs8490 Год назад

    Implemted this solution in C++, get a time limit exceeded error

  • @akhma102
    @akhma102 Год назад

    Wowow brother!