Target Sum - Dynamic Programming - Leetcode 494 - Python

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

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

  • @abhishekpawar8458
    @abhishekpawar8458 2 года назад +75

    For future readers, pls note the difference between this problem and knapsack
    1. In Knapsack, there is no compulsion that each number should be included to achieve a sum
    2. In Knapsack, there are positive numbers. Hence, for this problem : in the base case (target = 0 and empty/non-empty set), we cant blindly initialise it to 1.

  • @mudd7522
    @mudd7522 3 года назад +74

    This is exactly the problem I was working on and hoping for a video. You are a saint, Neetcode.

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

      Same😭

  • @liairi6834
    @liairi6834 2 года назад +74

    six months ago I saw this video, and now i'm back to learn this solution again : (

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

      Did you get it ?)

    • @Harish-rz4gv
      @Harish-rz4gv Год назад +2

      No problem, we all forget solutions

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

      +1

    • @shankysays
      @shankysays 10 месяцев назад

      i have a much simpler approach, suppose we divide the numbers in s1 and s2 sets. so s1+s2 = sum which we already know. s1-s2 is already given which is target difference. now add the two eqn and we get 2s1= sum+target. now all we need to do is find how many such s1 set exist, . thats the answer. this is basically subset sum problem.

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

      I had forgotten the coin change solution, dp isn't very intuitive.

  • @yizhang7027
    @yizhang7027 2 года назад +15

    I never realized how powerful decision trees are until I saw your videos.
    Thank you my prophet.

  • @7Ibby
    @7Ibby 3 года назад +29

    Hi, big fan here. I solved this problem in a different way and it runs quite efficiently. I just use a dictionary (initialized with 1 zero so that the first number in the nums array has something to compare against) and iterate over the nums array, and then I use another dictionary to store all the ways the numbers in the dp dictionary, "n", can change given the number from the nums array, "new_dp[n+/-num]", while keeping track of how many ways that new number can be made "dp[n]". Then all you have to do is return dp[target] since it holds how many ways that number can be achieved.
    def findTargetSumWays(self, nums, target):
    dp = defaultdict(int)
    dp[0] = 1
    for num in nums:
    new_dp = defaultdict(int)
    for n in dp:
    new_dp[n+num] += dp[n]
    new_dp[n-num] += dp[n]
    dp = new_dp
    return dp[target]

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

    my solution using the bottom up approach:
    class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
    dp = {}
    dp[0] = 1
    for n in nums:
    newdp = {}
    for key in dp:
    if (key + n) in newdp:
    newdp[key + n] += dp[key]
    else:
    newdp[key + n] = dp[key]
    if (key - n) in newdp:
    newdp[key - n] += dp[key]
    else:
    newdp[key - n] = dp[key]
    dp = newdp
    return dp.get(target, 0)

  • @sathyanarayanankulasekaran5928
    @sathyanarayanankulasekaran5928 3 года назад +8

    i tried both the ways, recursion-brute force and tis dp caching...for this array input, there is not much difference, bt when u increase the size of the array, you can see the DP magic in elapsed time..thank you

  • @benalfred42
    @benalfred42 3 года назад +29

    I'll be applying to faang companies on jan-feb; it was a blessing finding ur channel. Thanks bud :")

  • @gametech7046
    @gametech7046 2 года назад +13

    Hey there. Great solution but I wanted to know that will this solution be accepted in coding interviews or they might ask us to improve it to the bottom up/tabulation method. I understand those memoization solutions and am pretty comfortable with those and they also get accepted on leetcode. Please reply as I also want to crack those FAANG interviews just like you did. And thank you for all the efforts you put in those videos!

    • @knanzeynalov7133
      @knanzeynalov7133 7 месяцев назад +1

      Generally they look for tabular method because it is harder

  • @dheepthaaanand3214
    @dheepthaaanand3214 21 час назад

    To clarify, the dp pair is storing the number of ways starting at index i to sum to the given original total with total already in hand

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

    Hey does someone know if we can implement a tabulation solution to this problem? If not, how do we determine if a problem can or can't have tabulated solution??

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

    U a God. Finally been waiting for this video!

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

    I got the hang of recursive DFS thanks to your videos with crystal clear explanations :0
    Thanks a lot!!!

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

      hi. can you provide me the link ?

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

      @@jesuschrist8590
      ruclips.net/video/pfiQ_PS1g8E/видео.html&ab_channel=NeetCode

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

    A way to massively reduce the memory complexity (at a small price of 10 milliseconds more runtime) is for some reason using all the problem's parameters (plus the cache hashmap) as inputs to our helper function's parameters:
    class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
    cache = {}
    return self.dp(nums, 0, 0, target, cache)
    def dp(self, nums, index, sum, target, cache):
    if (index, sum) in cache:
    return cache[(index, sum)]
    if (index == len(nums)):
    if (sum == target):
    return 1
    else:
    return 0

    cache[(index, sum)] = self.dp(nums, index + 1, sum + nums[index], target, cache) + self.dp(nums, index + 1, sum - nums[index], target, cache)
    return cache[(index, sum)]
    Solution in video: 264 ms, 37.6 mb
    This solution: 274 ms, 17.4 mb

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

      Tried this, this is freaking huge reduction in memory footprint 🤯. Why though?

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

      @@bhargavsangani2901 No idea, probably has to do with how LeetCode handles memory initialization, probably passing as parameters declares them "once"/less frequently VS the same batch of newly initialized memory each run of each test?

  • @ywl.5465
    @ywl.5465 Год назад +4

    Backtracking works since nums size

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

    just a small question is the approach described here is actually a backtracking approach ? I saw the earlier n-queen problems and similar backtracking , we prune the path we tried for solution.
    If someone can help me clearing my doubt about this would be highly appreciated.

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

    For those looking for a true DP solution with no recursion:
    class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
    total_sum = sum(nums)
    # Check if (target + total_sum) is odd, or target is out of bounds
    if (target + total_sum) % 2 != 0 or target > total_sum or target < -total_sum:
    return 0
    # Calculate the subset sum we are looking for
    subset_sum = (target + total_sum) // 2
    # DP array, dp[j] will store the number of ways to get sum j
    dp = [0] * (subset_sum + 1)
    dp[0] = 1 # There is 1 way to get sum 0 (by picking no elements)
    for num in nums:
    # Traverse backwards to avoid overwriting previous states
    for j in range(subset_sum, num - 1, -1):
    dp[j] += dp[j - num]
    return dp[subset_sum]

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

      # The problem can be rephrased as finding two subsets of the array such that their difference equals the target sum. If you denote the sum of the positive subset as S1 and the sum of the negative subset as S2, you want:
      # S1-S2 = target
      # S1 + S2 = sum(nums)
      # S1 = (target + sum(nums))/2
      # The problem then reduces to finding the number of ways to get a subset with sum S1. If (target + sum(nums)) is odd, there is no valid S1, so you return 0. Otherwise, you use a DP array to count the number of ways to achieve the sum S1.

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

      @@pabloj1336 Thanks for explaining your solution 😄

  • @itenigneer21
    @itenigneer21 6 месяцев назад +1

    Don't you think putting a bound check on '+' when total is higher than desired target will avoid unwanted branching ?
    Please do comment whenever you get time..

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

    NeedCode must know this, just maybe share with others. Compared with caching, Bottom-Up approach can reduce the space complexity to O(sum(nums)).

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

    f(x, curr_sum) = {
    1, if x == len(nums) and curr_sum == target,
    0, if x == len(nums) and curr_sum != target,
    f(x + 1, curr_sum + nums[x]) + f(x + 1, curr_sum - nums[x]), otherwise
    }

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

    Found this bottom up solution on leetcode which is very efficient:
    res = {0:1}
    for num in nums:
    temp = {}
    for curSum in res:
    temp[curSum + num] = temp.get(curSum + num,0) + res[curSum]
    temp[curSum - num] = temp.get(curSum - num,0) + res[curSum]
    res = temp
    return res.get(target,0)

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

    man i just went to solve this this morning and you posted this yesterday. nice man
    also have u thought of making a meme channel called yeet code

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

    such concise explanantion! Thank you so much !

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

    Tabulation code in java
    public int findTargetSumWays(int[] nums, int target) {
    int sum=0;
    for(int i:nums){
    sum+=i;
    }
    if(Math.abs(target)>sum) return 0;
    //Let s1 and s2 be 2 subsets who's diff is target T and sum is S then
    //s1 +s2 =S
    //s1-s2 =T
    // 2*s1 = S+T //add both equations
    //2*s2 = S-T // subtract both
    //from above 2 equations its clear both shoud be even , as they are mutiple of 2 ,
    //hence this condition
    if( (target+sum) %2!=0 || (sum-target)%2!=0) return 0;
    int reqSum=(-target+sum)/2;
    return subsetSum(nums,nums.length,reqSum);
    }
    int subsetSum(int a[], int n, int sum){
    // Initializing the matrix
    int dp [] [] = new int [n][sum + 1] ;
    if(a[0]

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

    Isn't this technically just DFS since there is no search pruning. We aren't discarding partial solutions early. That said, the definitions of backtracking often seem to largely overlap with DFS or made straight synonymous with DFS. Please correct me if my understanding is wrong.

    • @idemchenko-js
      @idemchenko-js 3 года назад +5

      I think you're right. It's a straightforward DFS with caching

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

      This was confused me as well

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

    do you prefer using top down approach?

  • @CodingWorld202
    @CodingWorld202 6 месяцев назад +1

    everyone at first talking about market. Sad reality but

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

    can the time complexity be 2^n, cause each element in the array has 2 options, either to add it or subtract it. And can anyone explain how the the bottom-up approach is implemented. Couldn't understand the one in the solution.

  • @rishabhmalhotra6474
    @rishabhmalhotra6474 7 месяцев назад

    for me I was able to come with recursive solution, no problem at all but not able to come with dp approach as was not able to find how the states would be saved and it does happen with me a lot.
    any idea on how to become better at this

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

    I believe it can be solved with 1D DP array as well.

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

    Very nice explanation

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

    Is it possible to do this using a bottom up approach like you do with alot of other DP problems?

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

      And if not can you explain why you use one over the other in certain situations

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

    I did it!

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

    Great video. Thank you for taking the time to make it. One quick question. I understand the solution other than what is happening at line 9. Why do we return dp[(i, total)]. I under stand that we have just checked if the tuple is in the dict as a key pair, but why do we return it? If you run the code without the line in leetcode it still passes, so I just want to understand.
    Thanks to anyone who can help!

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

      dp is like a cache for storing previous results, inorder to avoid going through the entire computation again, we just return dp[(I, total)] that has already been previously computed

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

    What's the time complexity of this solution?

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

    why is the time complexity O(m*n) and not O(m + n) since if there are two factors influencing the time complexity of a method we take the one with the highest complexity?

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

    I really liked your videos. Can you provide us the Java solutions as well.

    • @nguyen-dev
      @nguyen-dev 2 года назад +2

      why do you need java solution? If you cannot write the solution in your programming language after watching the video, it means something else is wrong. Providing the solution in java will not help you.
      PS: I don't know python.

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

    Very clean and easy explanation . Thanks a lot

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

    What does the tabulation DP solution look like?

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

      heres's mine i did...
      class Solution:
      def findTargetSumWays(self, arr: List[int], T: int) -> int:
      dp=[[0 for i in range(2*sum(arr)+1)] for _ in range(len(arr))]
      index_start=sum(arr)
      if Tindex_start:
      return 0
      #iterate over possible solutions
      #Base Condition
      dp[0][index_start+arr[0]]=1
      dp[0][index_start-arr[0]]+=1

      for i in range(1,len(arr)):
      for j in range(-sum(arr),sum(arr)+1):
      if j-arr[i]>=-sum(arr):
      dp[i][index_start+j]+=dp[i-1][index_start+(j-arr[i])]


      if j+arr[i]

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

    Hello sir, I'm a beginner to ur channel. Plz let me know what is the right way or right approch to see coding question

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

    What is line number 11 and 12 doing?

  • @hwang1607
    @hwang1607 8 месяцев назад

    I think im starting to get this a little bit

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

    super helpful

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

    I do not understand dp[(i, total)] = backtrack(i+1, total+nums[i])+backtrack(i+1, total-nums[i]). How to store total number of solution? Could you or someone explain it to me?

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

      Two recursive calls are made, one adds the current item, the other subtracts it. Each of these choices creates a new path to explore, but eventually when that path has been fully explored, it will return a value (if there is no way to use any of the numbers after i, that can make the current total == target, then it returns 0. But if there were one or more ways, it would return that value). Now imagine this has happened from the very bottom, all the way back to the top, and we're back to our very first call, that means every other node in the tree except the very first one has been evaluated, therefore we can just add the results of both choices.

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

      @@avenged7ex This explained it perfectly, thanks.

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

    GOOD VIDEO

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

    Can you share the solution for "688. Knight Probability in Chessboard " using dp

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

    Thanks a lot

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

    no tabulation for this problem?

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

    I understand these videos but when it is time to solve on my own, I won't get the intuition at all.
    Anybody else in the same boat as me?

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

    Can it be solved using bottom up DP? Why? Why not?

    • @kaushik.aryan04
      @kaushik.aryan04 Год назад

      it can be see leetcode official solution

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

      def findTargetSumWays(self, nums: list[int], target: int) -> int:
      # the key is the current sum, the value is the number of possible expressions
      dp: dict[int, int] = {0: 1}
      for num in reversed(nums):
      dp_next: dict[int, int] = {}
      for cur_sum, count in dp.items():
      dp_next[cur_sum + num] = dp_next.get(cur_sum + num, 0) + count
      dp_next[cur_sum - num] = dp_next.get(cur_sum - num, 0) + count
      dp = dp_next
      return dp.get(target, 0)

  • @hwang1607
    @hwang1607 8 месяцев назад

    Is there a 2d array solution for this

  • @CS_n00b
    @CS_n00b 8 месяцев назад +1

    Is this backtracking? I would’ve thought this is just dfs

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

    i dont use python, why are you returning dp[I,total] ?

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

      He returns dp[(i, total)], those '()' are important. In Python wrapping item(s) in brackets converts it to a tuple. This allows the index and total to be stored as a unique key within the hashmap

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

    why did you call backtrack(0,0 ) should it not be backtrack(0,target)??

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

      Basically, you start with the index at 0 and the total argument at 0. You are accumulating the result as you go from index to index. If you see the base case, the if condition checks when index i == len(nums) which means we have processed all the elements in the array, then we check if the total == target; if we achieve this, we return 1, otherwise, we didn't succeed and thus return 0. So start the call with backtrack (index=0, total=0), and total accumulates to be equal to target if the path is successful.
      Hope this helps.

  • @shankysays
    @shankysays 10 месяцев назад

    i have a much simpler approach, suppose we divide the numbers in s1 and s2 sets. so s1+s2 = sum which we already know. s1-s2 is already given which is target difference. now add the two eqn and we get 2s1= sum+target. now all we need to do is find how many such s1 set exist, . thats the answer. this is basically subset sum problem.

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

    It would be nice to explore the bottom up dp solution for this too.

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

    2400. Number of ways to reach a point after exactly k steps . Can u help with this with proper explanation.

  • @alexandersmirnov4274
    @alexandersmirnov4274 11 месяцев назад

    that is not dp solution? its just recursion + mem

  • @QuantizedFields
    @QuantizedFields 7 месяцев назад

    Can't see any relation between your code and the explanation provided earlier. They look completely unrelated.

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

    anyone with solution in cpp or datatype to be used in cpp for dictionary?????

  • @Ash-fo4qs
    @Ash-fo4qs 2 года назад +1

    c++ code plz

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

      ```
      class Solution {
      public:
      map m ;
      vector nums ;
      int n;
      int target ;
      int backtrack(int index ,int total){
      if(index == n){
      return total == target ? 1 :0;
      }
      auto findcomb= m.find({index,total});
      if(findcomb!=m.end()){
      return findcomb->second ;
      }
      return m[{index,total}] =
      backtrack(index+1,total+nums[index])
      +backtrack(index+1 ,total-nums[index]);
      }

      int findTargetSumWays(vector& nums1, int target1) {
      nums = nums1;
      target = target1 ;
      n = nums.size();
      return backtrack(0 ,0);
      }
      };
      ```

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

      translate it yourself