Things to keep in mind while submitting code on Leetcode: 1. check if (sum+d)%2!=0 becuase if their sum is odd then there cannot be two partitions. 2. check if sum
@@abhinavgupta6730 We are initialising first column to 1, assuming there is only 1 way to make subset sum equal to 0, i.e. null subset, BUT this fails if we have 0's as elements of array. If we have a single 0 present in the array, then the subsets will be '{}, {0}' whose sum will be 0. Hence, there can be more than 1 way to make sum==0. FIX: Don't initialise the first col to be 1. Everything will be initialized to 0 except the first cell in the table i.e. dp[0][0]=1. AND j will start from 0 instead of 1.
source : pinned comment under tech dose video For those who has problem with test case [0,0,0,0,0,0,0,0,1], target = 1. The solution doesn't consider presence of "0"s in the array. Why the output is different ? Because, if we have "0", then, it can have +0 and -0 and still will not effect the sum of a set. For example: Target value is = 2 1) {0,2} = {+0,2}, {-0,2}. Ans: 2 But if we increase number of 0s, 2) {0,0,2} = {+0,+0,2}, {+0,-0,2}, {-0,+0,2},{-0,-0,2} . Ans: 4 So, if you observe, your answer increase by (2^number of 0s) i.e. pow(2,number of zeros). So, make a small change as follows: 1) on count of subsetsum function, if(nums[i-1] > j ) => change to: if (nums[i-1] > j || nums[i-1] == 0) dp[i][j] = dp[i-1][j]; //make no change and put the previous value as it is in the next subproblem. (I.e. 2, in example above) And then at the end, you answer will be return (int)Math.pow(2, number of 0s) * dp[nums.length][target] ; Also, other cases we need to handle is: if (S > sum || (sum + S) % 2 != 0){ //S is target return 0; }
You taught soooo well in the previous lectures that when you stated the question in the video, I paused it and found the solution on my own in just 2 minutes. And it worked perfectly. That clearly shows how great you teach. Cheers!
@@shyamjiwashcare better change the initialization condition of the original subset sum count problem. You can set t[j][0]=pow(2,zerocount) where zerocount is the number of zeroes encountered in first j elements of the array.
@@TheAdityaVerma can we do like this, i know this is a bit lengthy but just asking, constructing 2d matrix of size a[n+1][2*(sum of elements) +1] this 2*sum of elements ranges from -(array sum) to +(array sum)
The explanation is exquisite. Here are a few point some one might miss in online submission 1. sum+diff is a odd number 2. sum+diff is negative number In both of above return 0; 3. array has 0's in that case count number of zeros and push non zero elements in a new array solve for this new array. let this answer be x; then return x * pow(2,count of zeros)
@@humbleguy9891 (sum + diff) must be even. As we derived - 2*s1 = sum + diff [ (s1 + s2) = sum, (s1 - s2) = diff => sum + diff = s1 + s2 + s1 -s2 = 2*s1, which is always even] Why sum + diff < 0 ? Problem says nums[i] > 0, so, sum > 0 [sum of all +ve numbers] Now, we know the range of all subset sum's are 0 < sum of n[i] < sum. Say we choose all -n[i], which will make the range as - sum of (-n[i]) = -sum. So, target cannot be less than -sum => target + sum > 0
I used to sit hours for solving dp problems. I used to not get any idea for solving them. Eventually, I end up watching editorials and see others codes I can't understand anything I used to draw matrics and figure out how they did but I was unable to understand. Now I am happy that this was all past. I solved all the six problems just after watching the first 3 videos of the knapsack. Your explanation was superb bro. I fell in love with dp. Now I got confidence that I can ace in interviews. This is all because of you. Big Thanks 🙏️🙏️
bhaii ek baar mere solution mein mistake bta do class Solution { private: int Cnt(int n, vector& weight, int sum) { int t[n + 1][sum + 1];
for (int i = 0; i < n + 1; i++) { for (int j = 0; j < sum + 1; j++) { if (i == 0) { t[i][j] = 0; } if (j == 0) { t[i][j] = 1; } } } for (int i = 1; i < n + 1; i++) { for (int j = 1; j < sum + 1; j++) { if (weight[i - 1]
Trust me if you came this far in this series no one can stop you to solve A,B,C on codeforces , the dp taught here is more than enough for those C , i was getting stuck several times in the past due to my fear of DP , after roaming for about 5 months ,alas I was finally able to develop dp logic for such problems.
If i have to sum it up I must say "You are the best of those who teaches college friends at midnight just before Exams".I love your work soo much please do more n more videos on Coding, bcz that's the thing that actually matters in placements .I don't think any teacher in any college teaches like this,Your way of telling things makes direct connection to us.Specially DP ,bro seriously hands down to you.
Happy teachers day to one of the best teachers I have come across 😊 Thanks for all the free and valuable content you have created...We need more people like you in the coding community...Please start making videos again - a humble request from an ardent subscriber of yours
I think the initialisation will also be different for target sum as 0s are also allowed as valid element in the array. Using the old method of initialisation is giving me WA. Instead i just initialised the dp array from 0 and did dp[0][0] = 1. And included 0th column i.e j=0 while calculating the count for the subsetsums.
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: if abs(target) > sum(nums): return 0 # nums = [10], target = -100 s1 = (target + sum(nums)) // 2 # 2 * s1 = (target + sum(nums)) => as (target + sum(nums)) is a multiple of 2 so it must be an even number if (target + sum(nums)) % 2 != 0: return 0 dp = [[0]*(s1+1) for i in range(len(nums) + 1)] for j in range(s1 + 1): dp[0][j] = 0 for i in range(len(nums)+1): dp[i][0] = 1 # change values of remaining dp starting from (1, 0) to (len(nums), s1) for i in range(1, len(nums) + 1): for j in range(s1 + 1): if nums[i - 1]
Memoized solution for this is way too easy. dp={} # a map def util(a,n,k): key=str(n)+" "+str(k) if key in dp: return dp[key] if not n: dp[key]= 1 if k==target else 0 return dp[key] dp[key] = util(a,n-1,k+a[n-1])+util(a,n-1,k-a[n-1]) return dp[key]
great explanation, just love it. Would like to add some points to this solution. 1. initialise the dp array with dp[0][0]=1 and rest of the elements of 0th row as 0 i.e. dp[0][1....(target+totSum)/2]=0 and while iterating through the dp array, start the column from 0 and not from 1. This is done to take care of 0s present in the given vector. 2. I forgot to consider one edge case when the target
Dude, with the concepts you taught in subset sum, I was able to write the recursive solutions for all its variations problems in a minute or two. Kudos 🙌
ACCEPTED ON LEETCODE class Solution { public: int findTargetSumWays(vector& a, int target) { // Edge case when only one element is present in array if (a.size() == 1) { if (abs(a[0]) == abs(target)) return 1; else return 0; } // We will solve problem considering there is no zeroes in the input array, and we will deal with it in the last // To count the number of zeroes int z = 0; for (int i = 0; i < a.size(); i++) if (a[i] == 0) z++; int asum = accumulate(a.begin(), a.end(), 0); // Because the sum of a subset can't be in decimals if ((asum + target) % 2 == 1) return 0; // This is the given sum, of which we have to find the number of count of subsets with sum equal to given sum int t = (asum + target) / 2; // Since we are dealing with only positive integers, so sum of a subset can't be negative if (t < 0) return 0; // DP Array int dp[a.size() + 1][t + 1]; // Initialising DP Array for (int i = 0; i
why nt dp apporach work for test cases like [0,0,0,0,0,0,0,1] with a target 1 or [0,0,0,0,0,0,0,0,0] with a target of 0 : other side recursive and memoization code works fine for these type of cases . please answer!
[0,0,0,0,0,0,0,0,1] 1 on this test case your process will not work , when test case will have x number of zeros , then you have to so return pow(2,x)*ans ( this ans is answer which we will get by that the above approach) . , by the thanks Aditya , Hare krishna
I don't know how to thank you man. I have never understood Tabulation on my own in my college life and you made it smooth like butter.. I wish I found your playlist sooner ❤
for those who is getting wrong answer for input with zeros element. try to consider sum 0 as well. In that case you for empty set and sum 0, there will be 1 count so initialise t[0][0] = 1. and while counting if you remember inner loop tells that sum upto J. So for sum = 0, we need to start that loop from instead of 1.
Engrave this in stones and history will witness that best ever tutorials created for Dynamic Programming on entire planet was created by Aditya Verma. Period.
1-1+1+1+1=3 can be written as 1+1+1+1=3+1, 4=4. So if we count find counts of subsets of sum 4 that can automatically be written like this. generally, the number of count of subsets having sum (sum(nums)+target)//2 gives the required answer. If target > sum(nums) or if target+sum(nums) is odd then we cannot have any subsets like this.
You are amazing. I first wrote a solution using Input output method in recursion but then had to watch your previous video to reach this solution. This is how people write beautiful solutions after watching one video of yours :) class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: W = sum(nums) + target if W % 2 != 0 or W < 0: return 0 W = W//2 N = len(nums) t = [[-1 for _ in range(W+1)] for _ in range(N+1)] def solve(ip, N, W, t): if N == 0: return 1 if W == 0 else 0 if t[N][W] != -1: return t[N][W] if ip[N-1]
Aditya, your playlist is amazing and helping me understand DP in much easier way. Just one observation wrt this problem which I observed while coding is that program gives wrong o/p if (targetSum+arrayTotalSum) is odd
Great video. Just 1 thing to take care. Suppose array is {1,0, 2, 0, 0} and target is 1, then the possible solutions are: {-1, 0, +2, 0, 0} , every 0 can be asssigned + or -ve sign, so total possibilies = 2^3 = 8 If we reduce it to find the subsets of sum 1 then its solutions are: {-1, 2} {-1, 0, 2} {-1, 0, 2, 0} {-1, 0, - 2, 0, 0} Answer = 4 So the base condition when sum == 0 needs to be updated according to the problem. Please tell what are your views on it. @Aditya Verma
the way you explaining any problem is really uniques.there are multiples hard topics that really hard to learn but now I am completey understatnd the topic.and also I can solve various problem based on this.
@@TheAdityaVerma also in sub set sum count problem you haven't discussed case where 0 are included [1,0,0,0] gives wrong answer but [0,0,0,1] gives correct please check bro.
Dhanyaa ho gurudev g....kaha hai aapke paawan charan........ye logic to sch me hmare dimag me jindagi me aata hi nhi.....mja aane lga aapki videos dekh dekh k...... :)))
Hello , aditya. At first i want to thank you for your dp playlist. This code should be like this like your explanation and it works fine. class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: n=len(nums)
tar= (target + sum(nums))//2 t=[[0]*(tar+1) for _ in range(n+1)] for i in range(n+1): t[i][0]=1 if sum(nums) < abs(target): return 0 for i in range(1,n+1): for j in range(1, tar+1): if nums[i-1] > j: t[i][j]= t[i-1][j] else: t[i][j]= t[i-1][j] + t[i-1][j-nums[i-1]] return t[n][tar] In leetcode there is a problem about this. there input is like that [0,0,0,0,0,0,0,0,1] and target is 1. Expected output is 256. But this code gives output 1. Any help will be appreciated.
Wrote a recursive code and used dictionary(hashmap) instead of 2D matrix, got accepted on leetcode, but want to know is there any issue in using hashmap in interviews along side top down approach. Is bottom up the preferred solution expected in interviews ?
I have never solved DP problems this easily. Just in one go, I was able to solve all 11 problems till now. I am not believing myself that I was able to solve DP problems this easily. I want to show my gratitude some how. Please share some way to compensate .
In subset sum problem: +1+1+2-3 isequal to -1-1-2+3 as the set is same But in target sum +1+1+2-3 and -1-1-2+3 both are different as the order of signs are changed
for those who is getting wrong answer for input with zeros element. try to consider sum 0 as well. In that case you for empty set and sum 0, there will be 1 count so initialise t[0][0] = 1. and while counting if you remember inner loop tells that sum upto J. So for sum = 0, we need to start that loop from instead of 1. CREDIT: @pueshpendarsharma
In the previous question solution we took a range where one end was 0 and the other end was Sum of all values but here in thid problem the ranges would be different, one end would be the sum of all elements by taking all as negative and one end would be the sum of all. So how can we handle the negative end in the Top Down approach?
Tell me if I'm right Efficient use of dp matrix instead of counting 0's and multiplying answer with pow(2,count) : We have to initialize the first column of dp matrix carefully. dp[0][0] means sum 0 considering first 0 elements of array a dp[1][0] means sum 1 considering first 1 elements of array a so if any element of the array is 0 (a[i-1]==0) then dp[i][0] = 2*dp[i-1][0] as now we will have 2 choices (to include the 0 and to not include it so previous multiplied by 2). else if(a[i-1]!=0) then make it equal to the previous one, i.e., dp[i][0]=dp[i-1][0] . complete code for initialization is : dp[0][0]=1; for(int i=1;i
just took a minute or so to realize that it was same as the previous problem.. as he said in starting that he want us to think of the solution rather than mug it up..so clearly i can see that impact in this video!!..
SHITTTTTTTTTTTTTTTTTTTTTTTTTT.... How can someone think so good.. You're my saviour man.. If I achieve something big.. I'll surely come to you to give you a token of love by all the strugglers out here!
Is it possible to convert this problem to DP from recursion code? I think it is not possible, basically Recursion and DP code are different for this problem statement?
Bhai your explaination are best!! But please last main ek page pr wo ques kr diya kro jiske liye video bnaya h...ek ques k liye mujhe aapke 4-4 video dekhne pd gye..itne se ques k liye 1 ghanta lg gya. So atleast at the end 2 min kewal usi ques ka solution likh do jiske liye video bnaya h.
Leet code problem .... there's an error if the test case contains zeros . Here is mine submitted recursive solution : n is the size of array and initially sum = 0 ; int solve(vector &nums , int target , int n , int sum) { if(n==0) { if(sum == target) return 1; else return 0; }
return solve(nums ,target , n-1 , sum + nums[n-1]) + solve(nums , target , n-1 , sum - nums[n-1]);
For those who has problem with test case [0,0,0,0,0,0,0,0,1], target = 1. Just Start your second for loop from 0 instead of zero it will take care of everything n think about it little bit you will get this.
0's must be handled separetly. 1. create another array with non-zeros, find solution as taught in video. 2. count zeros in original input and final answer will be ANS * pow(2,zero_count)
bhaiya it is not working with arr[i] == 0. For example suppose array = [0,0,0,0,0,0,0,0,1] and target sum is 1 then answer is 256 but this approach is giving 1. I am doing everything right and this approach is ignoring the 0 elements.
@aditya: can we get your hand written notes which you making during video. I have finished the 0-1 napsack series, now before moving to unbounded napsack I want to practice 0-1 napsack problems.
After reading the problem statement i tried to think of Recursive Backtracking approach earlier we solved problems by including and excluding at every we have 2 possible cases : positive and negative try to draw the recursion tree for this approach(same as inclusive and exclusive ) In each case, after everytime you reach end of the array just add them and check whether it is leading to given target if so increment the count and return the count . class Solution { static int c=0; public int findTargetSumWays(int[] nums, int target) { c=0; find(nums,target,0); return c; } public static void find(int nums[],int target,int idx){ if(idx==nums.length){ int sum=0; for(int i:nums){ sum+=i; } if(sum==target){ c++; } return ; } nums[idx]=nums[idx]*(-1); find(nums,target,idx+1); nums[idx]=nums[idx]*(-1); find(nums,target,idx+1); } } Note: this might not be optimal but this is enough to pass all test cases in Leetcode 494
I think you have missed the base case If say, givem array is [0,0,0,0,0,0,0,0,1] and the difference is 1 by your logic it will give wrong output Please check for the base if array containing zero
I hv one more approach we can use count of subset with target sum except we have 3 possibilities : add, substract and exclude. def subset_sum_with_sign_change ( nums : list , n : int, target_sum : int): if target_sum == 0: return True if n == 0: return False
return subset_sum_with_sign_change ( nums , n - 1, target_sum - nums [n - 1] ) or \ subset_sum_with_sign_change ( nums , n - 1, target_sum ) or \ subset_sum_with_sign_change ( nums , n - 1, target_sum + nums [ n - 1 ] ) def dp_subset_sum_with_sign_change ( nums : list, n : int, target_sum : int ): dp = [ [ 0 for _ in range ( sum ( nums ) + 1 ) ] for _ in range ( n + 1 ) ] def initialize_dp_table(): nonlocal dp for num_index in range ( n + 1 ): for subsum in range ( sum ( nums ) + 1 ): if num_index == 0 and subsum != 0: dp [ num_index ] [ subsum ] = 0 if subsum == 0 or subsum == sum(nums): dp [ num_index ] [ subsum ] = 1 def fill_dp_table(): nonlocal dp for num_index in range ( 1 , n + 1 ): for subsum in range ( 1 , target_sum + 1 ): dp [ num_index ][ subsum ] = dp [ num_index - 1 ] [ subsum - nums [ num_index - 1 ] ] +\ dp [ num_index - 1 ] [ subsum + nums [ num_index - 1 ] ] +\ dp [ num_index - 1 ] [ subsum ] initialize_dp_table() fill_dp_table() for row in dp: print ( row ) return dp [ n ] [ target_sum ]
public class targetSum { // Same problem hai ye kyoki agar tu + and - assign kar raha hai toh tu common // sign bahar nikalkr do subset ke difference mai show kar sakta hai same cheez, // i.e S1-S2. // Function to count subsets with a given difference in sum public static int CountSubsetsWithGivenDiff(int arr[], int diff) { // Calculate the total sum of the elements in the input array int sum = 0; for (int i = 0; i < arr.length; i++) { sum += arr[i]; } // Calculate the subset sum required to achieve the given difference int subsetSumToFind = (diff + sum) / 2; // Aditya Verma Equations xD. // Use dynamic programming to count subsets with the desired sum return countSubsetsWithGivenSum(arr, subsetSumToFind); } // Function to count subsets with a given sum using dynamic programming public static int countSubsetsWithGivenSum(int[] arr, int sum) { int n = arr.length; int[][] dp = new int[n + 1][sum + 1]; // Initialize the base cases for (int i = 0; i
As already mentioned we need to take care of the case where 0's are present in the nums array and also one interesting corner which was left out. Case 1) Zeroes in array. For this we just need to make a small adjustment i.e include the base case 0 sum also which we were not including previously i.e. starting the column loop from 1. Now we need to start the column loop from 0 taking the 0 sum case also in consideration. Modified loop => for (int i = 1 ; i < n+1 ; i++) { for (int j = 0 ; j < sum+1 ; j++) { if (arr[i-1] [100] and target = -100. For this we need to take care that our sum is always less that absolute value of target. Modified code => if (sum < abs(target) || (target + sum) % 2 > 0) return 0;
Could you please explain the reasoning behind the corrective measures you took for case 1? How and why did taking j = 0 helps us resolve the problem? Thanks
@@HarshalDev You must understand what are these two loops for, these loops denote the states. i loop from 1 to n denote the number of elements I'm including in my sum calculation and j loop denote the target sum for those i elements ( a smaller sub problem of the orginal problem) For eg consider I'm at i = 3, j = 5 transition in the table. So it means I'm considering a target sum sub/shorter problem where the there are 3 elements and Target sum to find is 5. So when I start the loop from j = 0 instead of j=1 I'm taking into account the zero target sum sub problem too. Please let me know if it clears your doubt now..
if anyone facing some issue in leetcode question: int s1 = (sum+target)/2; // if(sum < abs(target)) ==> sum + target will become negative and index issue hoga if(s1 < 0){ s1 = (sum-target)/2; // if above problem, then we use the value of other subset .... simple } // Explanation /* s1 + s2 = sum s1 - s2 = target ----------------- 2s1 = sum + target => s1 = (sum + target)/2 => CASE 1 2s2 = sum - target => s2 = (sum - target)/2 => CASE 2 */ Use this as reference
bhaiya apka teaching mujhe acha lagta, bahut kuch shik raha hai . Mera ek request tha ki ek video placement preperation ke bare me kar saktha hai na, help hoga humko
Things to keep in mind while submitting code on Leetcode:
1. check if (sum+d)%2!=0 becuase if their sum is odd then there cannot be two partitions.
2. check if sum
An addition (sum+d > 0)
Can you please explain the logic behind your third point.
Thank you
@@abhinavgupta6730 We are initialising first column to 1, assuming there is only 1 way to make subset sum equal to 0, i.e. null subset, BUT this fails if we have 0's as elements of array. If we have a single 0 present in the array, then the subsets will be '{}, {0}' whose sum will be 0. Hence, there can be more than 1 way to make sum==0.
FIX: Don't initialise the first col to be 1. Everything will be initialized to 0 except the first cell in the table i.e. dp[0][0]=1. AND j will start from 0 instead of 1.
partition can be possible if sum is odd , partition will not be possible when (sum + d ) is odd
source : pinned comment under tech dose video
For those who has problem with test case [0,0,0,0,0,0,0,0,1], target = 1.
The solution doesn't consider presence of "0"s in the array. Why the output is different ?
Because, if we have "0", then, it can have +0 and -0 and still will not effect the sum of a set. For example: Target value is = 2
1) {0,2} = {+0,2}, {-0,2}. Ans: 2
But if we increase number of 0s,
2) {0,0,2} = {+0,+0,2}, {+0,-0,2}, {-0,+0,2},{-0,-0,2} . Ans: 4
So, if you observe, your answer increase by (2^number of 0s) i.e. pow(2,number of zeros).
So, make a small change as follows:
1) on count of subsetsum function,
if(nums[i-1] > j ) => change to: if (nums[i-1] > j || nums[i-1] == 0)
dp[i][j] = dp[i-1][j];
//make no change and put the previous value as it is in the next subproblem. (I.e. 2, in example above)
And then at the end, you answer will be
return (int)Math.pow(2, number of 0s) * dp[nums.length][target] ;
Also, other cases we need to handle is:
if (S > sum || (sum + S) % 2 != 0){ //S is target
return 0;
}
Man, thanks a lot. I just found your comment and even I asked the same question. Thanks for improving the answer !
This really helped!!
If we start the inner loop from j=0 instead of j=1 it automatically solves all the cases.
@@psthakur1199 This is real DP solution if one understands why :')
@@psthakur1199 can you explain why that works
yar jab aap logic decode karte ho na, smile aa jati hai chehre par :)
💯😂
Control bhai !!😄
💪💯
Bhaiya kaha place hue?
Sach me ....
Ye wala qn meine pehle try kar raha tha +/- picking leke...
Par jab logic dekha to😂😂
You taught soooo well in the previous lectures that when you stated the question in the video, I paused it and found the solution on my own in just 2 minutes. And it worked perfectly.
That clearly shows how great you teach.
Cheers!
can u tell that how u got submitted it to leetcode
Glad it helped, Do share please !!
@@ankuragarwal4014 count number of zeros (if you are talking about leetcode target sum problem) in the vector (say z) and return dp[ ][ ]*pow(2,z);
@@shyamjiwashcare better change the initialization condition of the original subset sum count problem.
You can set t[j][0]=pow(2,zerocount) where zerocount is the number of zeroes encountered in first j elements of the array.
@@TheAdityaVerma can we do like this, i know this is a bit lengthy but just asking, constructing 2d matrix of size a[n+1][2*(sum of elements) +1] this 2*sum of elements ranges from -(array sum) to +(array sum)
The explanation is exquisite.
Here are a few point some one might miss in online submission
1. sum+diff is a odd number
2. sum+diff is negative number
In both of above return 0;
3. array has 0's
in that case count number of zeros and push non zero elements in a new array
solve for this new array. let this answer be x;
then return x * pow(2,count of zeros)
can u please explain the logic of all the above 3 points? I am a noobie in DP.
Thank you very much @dakshveersinghchauhan613
@@humbleguy9891 (sum + diff) must be even. As we derived -
2*s1 = sum + diff [ (s1 + s2) = sum, (s1 - s2) = diff => sum + diff = s1 + s2 + s1 -s2 = 2*s1, which is always even]
Why sum + diff < 0 ?
Problem says nums[i] > 0, so, sum > 0 [sum of all +ve numbers]
Now, we know the range of all subset sum's are 0 < sum of n[i] < sum. Say we choose all -n[i], which will make the range as -
sum of (-n[i]) = -sum. So, target cannot be less than -sum => target + sum > 0
can u also explain his 3rd logic for arr with 0's why we r multiplying with power of its cnt@@saurav1018
We want similar playlist on trees and graphs . This playlist is pure gem
I used to sit hours for solving dp problems. I used to not get any idea for solving them. Eventually, I end up watching editorials and see others codes I can't understand anything I used to draw matrics and figure out how they did but I was unable to understand. Now I am happy that this was all past. I solved all the six problems just after watching the first 3 videos of the knapsack. Your explanation was superb bro. I fell in love with dp. Now I got confidence that I can ace in interviews. This is all because of you. Big Thanks 🙏️🙏️
For Leetcode 494. Target Sum, we need to handle 2 more conditions:-
if(sum < target) return 0;
if((sum+target)
Thank you bhai
bhaii ek baar mere solution mein mistake bta do
class Solution {
private:
int Cnt(int n, vector& weight, int sum) {
int t[n + 1][sum + 1];
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < sum + 1; j++) {
if (i == 0) {
t[i][j] = 0;
}
if (j == 0) {
t[i][j] = 1;
}
}
}
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < sum + 1; j++) {
if (weight[i - 1]
but 1 condition still doesn't work if target =-200 and n=[100]
@@bhavyaagrawal7098 It should work,
if(array_sum+d) array_sum:
return 0
if (d + array_sum) % 2 != 0:
return 0
@@bhavyaagrawal7098 You need to take absolute value for target. so initially make target = abs(target), and then solve.
Trust me if you came this far in this series no one can stop you to solve A,B,C on codeforces , the dp taught here is more than enough for those C , i was getting stuck several times in the past due to my fear of DP , after roaming for about 5 months ,alas I was finally able to develop dp logic for such problems.
what is the A,B,C problems? Could you please attach a link?
@@019_devarghachattapadhyay5 bruh , those are contest problems A , B and C are like a way of sequencing its not anu name.
After seeing this solun. I felt like "Rishta whi ,soch nai" xp
ha bhai, gangadhar hi shaktimaan hai !! 😂😂
@@TheAdityaVerma 🤣🤣🤣🤣
@@TheAdityaVerma ha.. ha..
@@TheAdityaVerma bhai some tc are not working
If i have to sum it up I must say "You are the best of those who teaches college friends at midnight just before Exams".I love your work soo much please do more n more videos on Coding, bcz that's the thing that actually matters in placements .I don't think any teacher in any college teaches like this,Your way of telling things makes direct connection to us.Specially DP ,bro seriously hands down to you.
Happy teachers day to one of the best teachers I have come across 😊 Thanks for all the free and valuable content you have created...We need more people like you in the coding community...Please start making videos again - a humble request from an ardent subscriber of yours
I think the initialisation will also be different for target sum as 0s are also allowed as valid element in the array. Using the old method of initialisation is giving me WA. Instead i just initialised the dp array from 0 and did dp[0][0] = 1. And included 0th column i.e j=0 while calculating the count for the subsetsums.
Will reach out to you soon in some free time. Till then keep watching !!
@@TheAdityaVerma i guess he is right, solving the question on leetcode i found a few things and constraints missing in your solution.
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
if abs(target) > sum(nums): return 0 # nums = [10], target = -100
s1 = (target + sum(nums)) // 2
# 2 * s1 = (target + sum(nums)) => as (target + sum(nums)) is a multiple of 2 so it must be an even number
if (target + sum(nums)) % 2 != 0: return 0
dp = [[0]*(s1+1) for i in range(len(nums) + 1)]
for j in range(s1 + 1):
dp[0][j] = 0
for i in range(len(nums)+1):
dp[i][0] = 1
# change values of remaining dp starting from (1, 0) to (len(nums), s1)
for i in range(1, len(nums) + 1):
for j in range(s1 + 1):
if nums[i - 1]
@@samirpaul2 because we need to handle the cases where multiple zeroes are there in the array which increases the number of subsets
Memoized solution for this is way too easy.
dp={} # a map
def util(a,n,k):
key=str(n)+" "+str(k)
if key in dp: return dp[key]
if not n:
dp[key]= 1 if k==target else 0
return dp[key]
dp[key] = util(a,n-1,k+a[n-1])+util(a,n-1,k-a[n-1])
return dp[key]
12 of 50 (24%) done! Nice revision on this one!
where are you nowadays buddy?
lets see@@aryangautam7506
1. smuggling cocaine
2. Directing XXX
3. Farmer 🪚 Protest
4. Dot net developer
great explanation, just love it. Would like to add some points to this solution.
1. initialise the dp array with dp[0][0]=1 and rest of the elements of 0th row as 0 i.e. dp[0][1....(target+totSum)/2]=0 and while iterating through the dp array, start the column from 0 and not from 1. This is done to take care of 0s present in the given vector.
2. I forgot to consider one edge case when the target
Hey dude can u explain why (target+totalSum)%2!=0, return 0 this condition is necessary.
@@fardeenalam6929 See reasons for both the edge conditions are:-
1. sum
thanks man...now it got accepted on leet code
@@kirtikhohal3313 Thanks for your explanation ☺
Dude, with the concepts you taught in subset sum, I was able to write the recursive solutions for all its variations problems in a minute or two. Kudos 🙌
ACCEPTED ON LEETCODE
class Solution {
public:
int findTargetSumWays(vector& a, int target) {
// Edge case when only one element is present in array
if (a.size() == 1) {
if (abs(a[0]) == abs(target))
return 1;
else
return 0;
}
// We will solve problem considering there is no zeroes in the input array, and we will deal with it in the last
// To count the number of zeroes
int z = 0;
for (int i = 0; i < a.size(); i++)
if (a[i] == 0)
z++;
int asum = accumulate(a.begin(), a.end(), 0);
// Because the sum of a subset can't be in decimals
if ((asum + target) % 2 == 1)
return 0;
// This is the given sum, of which we have to find the number of count of subsets with sum equal to given sum
int t = (asum + target) / 2;
// Since we are dealing with only positive integers, so sum of a subset can't be negative
if (t < 0)
return 0;
// DP Array
int dp[a.size() + 1][t + 1];
// Initialising DP Array
for (int i = 0; i
thank you mere bhai
why nt dp apporach work for test cases like [0,0,0,0,0,0,0,1] with a target 1 or [0,0,0,0,0,0,0,0,0] with a target of 0 : other side recursive and memoization code works fine for these type of cases . please answer!
[0,0,0,0,0,0,0,0,1]
1
on this test case your process will not work , when test case will have x number of zeros , then you have to so return pow(2,x)*ans ( this ans is answer which we will get by that the above approach) . ,
by the thanks Aditya , Hare krishna
I am falling in love with DP with every video of yours you explain so well thank you for making my fear turn into interest..😍
I don't know how to thank you man. I have never understood Tabulation on my own in my college life and you made it smooth like butter.. I wish I found your playlist sooner ❤
for those who is getting wrong answer for input with zeros element. try to consider sum 0 as well. In that case you for empty set and sum 0, there will be 1 count so initialise t[0][0] = 1. and while counting if you remember inner loop tells that sum upto J. So for sum = 0, we need to start that loop from instead of 1.
Engrave this in stones and history will witness that best ever tutorials created for Dynamic Programming on entire planet was created by Aditya Verma. Period.
Thanks mate ❤️
@@TheAdityaVerma bhai Patreon pe message nahi dekha aapne.
Agreed💯❤
1-1+1+1+1=3 can be written as 1+1+1+1=3+1, 4=4. So if we count find counts of subsets of sum 4 that can automatically be written like this. generally, the number of count of subsets having sum (sum(nums)+target)//2 gives the required answer. If target > sum(nums) or if target+sum(nums) is odd then we cannot have any subsets like this.
You are amazing. I first wrote a solution using Input output method in recursion but then had to watch your previous video to reach this solution.
This is how people write beautiful solutions after watching one video of yours :)
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
W = sum(nums) + target
if W % 2 != 0 or W < 0:
return 0
W = W//2
N = len(nums)
t = [[-1 for _ in range(W+1)] for _ in range(N+1)]
def solve(ip, N, W, t):
if N == 0:
return 1 if W == 0 else 0
if t[N][W] != -1:
return t[N][W]
if ip[N-1]
Aditya, your playlist is amazing and helping me understand DP in much easier way. Just one observation wrt this problem which I observed while coding is that program gives wrong o/p if (targetSum+arrayTotalSum) is odd
so return 0 for all those cases
Great video.
Just 1 thing to take care.
Suppose array is {1,0, 2, 0, 0} and target is 1, then the possible solutions are:
{-1, 0, +2, 0, 0} , every 0 can be asssigned + or -ve sign, so total possibilies = 2^3 = 8
If we reduce it to find the subsets of sum 1 then its solutions are:
{-1, 2}
{-1, 0, 2}
{-1, 0, 2, 0}
{-1, 0, - 2, 0, 0}
Answer = 4
So the base condition when sum == 0 needs to be updated according to the problem.
Please tell what are your views on it.
@Aditya Verma
Aapke video be bahut achhe hai Bhai. mein aapka bhakt hun. Trees aapse seekha hai
No doubt, this man has power that will make you fall in love with DP.
- Ketan Sisodiya
whenever i watch your video i am always like "WAAH KYA BAAT HAI" :)
the way you explaining any problem is really uniques.there are multiples hard topics that really hard to learn but now I am completey understatnd the topic.and also I can solve various problem based on this.
for i/p a[ ]=0,0,1 target sum=1 correct o/p is 4 this will give 1 because we are not considering 0's
subsets :
0,0,1
0,1
0,1
1
same problem, tried solving this question in leetcode and got wrong answer. found any solution?
Yeah, I check it 122/126 test cases are passing only, maybe I will upload a updated optimization for it soon !!
I think for this case what we can do is extract the number of 0s in the array and multiply our answer with 2^(number of 0s).
@@TheAdityaVerma also in sub set sum count problem you haven't discussed case where 0 are included [1,0,0,0] gives wrong answer but [0,0,0,1] gives correct please check bro.
@@kuskargupt2887 i think it wont work as for input 010 output is 2
Thank you so much i recognized by myself....this problem is variation of count the number of subset with a given difference
Dhanyaa ho gurudev g....kaha hai aapke paawan charan........ye logic to sch me hmare dimag me jindagi me aata hi nhi.....mja aane lga aapki videos dekh dekh k...... :)))
Hello , aditya. At first i want to thank you for your dp playlist.
This code should be like this like your explanation and it works fine.
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n=len(nums)
tar= (target + sum(nums))//2
t=[[0]*(tar+1) for _ in range(n+1)]
for i in range(n+1):
t[i][0]=1
if sum(nums) < abs(target):
return 0
for i in range(1,n+1):
for j in range(1, tar+1):
if nums[i-1] > j:
t[i][j]= t[i-1][j]
else:
t[i][j]= t[i-1][j] + t[i-1][j-nums[i-1]]
return t[n][tar]
In leetcode there is a problem about this. there input is like that [0,0,0,0,0,0,0,0,1] and target is 1. Expected output is 256. But this code gives output 1. Any help will be appreciated.
the entire series helps in developing the right thought process. Thanks for your efforts!
Wrote a recursive code and used dictionary(hashmap) instead of 2D matrix, got accepted on leetcode, but want to know is there any issue in using hashmap in interviews along side top down approach. Is bottom up the preferred solution expected in interviews ?
Can you please give a list of problems that are derived from knapsack pattern so that we can practice.
u thaught me most practical way of learning
I am glad it helped you. Please share and help this channel grow !!
zero handle karne wala case ek baar dekhna padega keval
Explanation Supeerrrrrrr se Upar!!
I have never solved DP problems this easily. Just in one go, I was able to solve all 11 problems till now. I am not believing myself that I was able to solve DP problems this easily. I want to show my gratitude some how. Please share some way to compensate .
sir can you please give a list of problems related to 0/1 knapsack other than these problems
In subset sum problem: +1+1+2-3 isequal to -1-1-2+3 as the set is same
But in target sum +1+1+2-3 and -1-1-2+3 both are different as the order of signs are changed
for those who is getting wrong answer for input with zeros element. try to consider sum 0 as well. In that case you for empty set and sum 0, there will be 1 count so initialise t[0][0] = 1. and while counting if you remember inner loop tells that sum upto J. So for sum = 0, we need to start that loop from instead of 1.
CREDIT: @pueshpendarsharma
In the previous question solution we took a range where one end was 0 and the other end was Sum of all values but here in thid problem the ranges would be different, one end would be the sum of all elements by taking all as negative and one end would be the sum of all. So how can we handle the negative end in the Top Down approach?
Tell me if I'm right
Efficient use of dp matrix instead of counting 0's and multiplying answer with pow(2,count) :
We have to initialize the first column of dp matrix carefully.
dp[0][0] means sum 0 considering first 0 elements of array a
dp[1][0] means sum 1 considering first 1 elements of array a
so if any element of the array is 0 (a[i-1]==0) then dp[i][0] = 2*dp[i-1][0] as now we will have 2 choices (to include the 0 and to not include it so previous multiplied by 2). else if(a[i-1]!=0) then make it equal to the previous one, i.e., dp[i][0]=dp[i-1][0] .
complete code for initialization is :
dp[0][0]=1;
for(int i=1;i
just took a minute or so to realize that it was same as the previous problem.. as he said in starting that he want us to think of the solution rather than mug it up..so clearly i can see that impact in this video!!..
SHITTTTTTTTTTTTTTTTTTTTTTTTTT.... How can someone think so good.. You're my saviour man.. If I achieve something big.. I'll surely come to you to give you a token of love by all the strugglers out here!
Bro seriously I haven't seen anybody teach DP like this. You are awesome bro. Hats off bhai. Matlab maza hi aa gya
the best dp lectures on yt frr
Pura same ques bas confusion hi confusion create krta h problem setter
Ab clr ho gya pura. Thank you sir
I never seen dp solving like this ,So Thanx for this videos.
Is it possible to convert this problem to DP from recursion code? I think it is not possible, basically Recursion and DP code are different for this problem statement?
Bhai your explaination are best!! But please last main ek page pr wo ques kr diya kro jiske liye video bnaya h...ek ques k liye mujhe aapke 4-4 video dekhne pd gye..itne se ques k liye 1 ghanta lg gya. So atleast at the end 2 min kewal usi ques ka solution likh do jiske liye video bnaya h.
Could you please also update the video along with covering the edge cases
Guys!! please "like" videos if you understood his concepts. now 93k views but only 3k likes.
At least he deserves 93K likes for his handwork.
Leet code problem .... there's an error if the test case contains zeros .
Here is mine submitted recursive solution :
n is the size of array and initially sum = 0 ;
int solve(vector &nums , int target , int n , int sum)
{
if(n==0)
{
if(sum == target)
return 1;
else
return 0;
}
return solve(nums ,target , n-1 , sum + nums[n-1]) + solve(nums , target , n-1 , sum - nums[n-1]);
}
You are a dynamic programming super star. (DPMan)
For those who has problem with test case [0,0,0,0,0,0,0,0,1], target = 1.
Just Start your second for loop from 0 instead of zero it will take care of everything n think about it little bit you will get this.
Solved the question after understanding the problem statement and before watching the solution 😎
Thank you very much. You are a genius.
Kindly redo the initialization part. It doesn't work when we deal with input containing 0.
Look at Rishab Sinha's solution. He covered those cases in the code he mentioned above.
Wow, brilliant, however, I solved this as a tree. All thanks to you!!
How did you solve using trees ? Could you give your solution?
can we also solve it by using count subset with equal sum by having condition(take positve sign and take negative sign) instead of take not take?
All the testcases are not passed for this question on leetcode !. could you plz provide us the code !
hey, here's my leetcode solution:-
int findTargetSumWays(vector& nums, int target) {
int sum=0,s,size;
for(int i=0;i
Can someone tell from where to practice different different problems(other then these 4) based on knapsack.
i solved this que without seeing this video just becasue i watched previous videos. thanks a lot bro .
0's must be handled separetly.
1. create another array with non-zeros, find solution as taught in video.
2. count zeros in original input and final answer will be ANS * pow(2,zero_count)
bhaiya it is not working with arr[i] == 0. For example suppose array = [0,0,0,0,0,0,0,0,1] and target sum is 1 then answer is 256 but this approach is giving 1.
I am doing everything right and this approach is ignoring the 0 elements.
@aditya: can we get your hand written notes which you making during video. I have finished the 0-1 napsack series, now before moving to unbounded napsack I want to practice 0-1 napsack problems.
if the array is [9,2,9] and the target element is 3 then why the output i am getting is 2 if i do not consider ((sum+target)%2!=0)return 0; case?
Wow Dude!!, Again as far as I keep coming ahead, just continue to amaze me.!! KudoS!!
Getting "Memory Limit Exceeded" in leetcode problem 494. Target Sum
did u solve the issue? if yes how?
Your every single video is a masterpiece..
Could anyone tell me what would be our approach if the target sum is -ve and the equivalent target sum is also negative
After reading the problem statement
i tried to think of Recursive Backtracking approach
earlier we solved problems by including and excluding
at every we have 2 possible cases :
positive and negative
try to draw the recursion tree for this approach(same as inclusive and exclusive )
In each case,
after everytime you reach end of the array just add them and check whether it is leading to given target
if so increment the count and return the count .
class Solution {
static int c=0;
public int findTargetSumWays(int[] nums, int target) {
c=0;
find(nums,target,0);
return c;
}
public static void find(int nums[],int target,int idx){
if(idx==nums.length){
int sum=0;
for(int i:nums){
sum+=i;
}
if(sum==target){
c++;
}
return ;
}
nums[idx]=nums[idx]*(-1);
find(nums,target,idx+1);
nums[idx]=nums[idx]*(-1);
find(nums,target,idx+1);
}
}
Note: this might not be optimal but this is enough to pass all test cases in Leetcode 494
Bhaii isko usse bhi toh kr skte hain na(check no. Of subset for given sum, aapne jo btaya tha) ?
Choice("+" yaa "-")
Practical learning is the best !, kudos to your hardwork and way of teaching sir !
Awesome !! You are a really good teacher !! Excellent playlist.
Does this work for if the target S is negative?
How do you actually return the valid subsets? I get how to find the count, but I'm not sure how you can find the subsets (1, 1, 2), (1, 3), (3, 1)...
o bhaiiii OP.....boom just a simple trick and problem solved .
the entire series helps in developing the right thought process
I dont think this code consider some test cases like target is greater than sum. Also if it has 0's.
Now I am getting confidence in dp after watching your dp videos. Thanks bro, OP🔥
I think you have missed the base case
If say, givem array is [0,0,0,0,0,0,0,0,1] and the difference is 1
by your logic it will give wrong output
Please check for the base if array containing zero
I hv one more approach we can use count of subset with target sum except we have 3 possibilities : add, substract and exclude. def subset_sum_with_sign_change ( nums : list , n : int, target_sum : int):
if target_sum == 0:
return True
if n == 0:
return False
return subset_sum_with_sign_change ( nums , n - 1, target_sum - nums [n - 1] ) or \
subset_sum_with_sign_change ( nums , n - 1, target_sum ) or \
subset_sum_with_sign_change ( nums , n - 1, target_sum + nums [ n - 1 ] )
def dp_subset_sum_with_sign_change ( nums : list, n : int, target_sum : int ):
dp = [ [ 0 for _ in range ( sum ( nums ) + 1 ) ] for _ in range ( n + 1 ) ]
def initialize_dp_table():
nonlocal dp
for num_index in range ( n + 1 ):
for subsum in range ( sum ( nums ) + 1 ):
if num_index == 0 and subsum != 0:
dp [ num_index ] [ subsum ] = 0
if subsum == 0 or subsum == sum(nums):
dp [ num_index ] [ subsum ] = 1
def fill_dp_table():
nonlocal dp
for num_index in range ( 1 , n + 1 ):
for subsum in range ( 1 , target_sum + 1 ):
dp [ num_index ][ subsum ] = dp [ num_index - 1 ] [ subsum - nums [ num_index - 1 ] ] +\
dp [ num_index - 1 ] [ subsum + nums [ num_index - 1 ] ] +\
dp [ num_index - 1 ] [ subsum ]
initialize_dp_table()
fill_dp_table()
for row in dp:
print ( row )
return dp [ n ] [ target_sum ]
Best DP course on internet!
real feel bhai, phle sirf naam suna tha aditya verma is famous for dp abb realise kr raha hu bhai
its failing for the input
[100] -100
in case array has negative numbers then?
Congratulations for 50k Subscribers
public class targetSum { // Same problem hai ye kyoki agar tu + and - assign kar raha hai toh tu common
// sign bahar nikalkr do subset ke difference mai show kar sakta hai same cheez,
// i.e S1-S2.
// Function to count subsets with a given difference in sum
public static int CountSubsetsWithGivenDiff(int arr[], int diff) {
// Calculate the total sum of the elements in the input array
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
// Calculate the subset sum required to achieve the given difference
int subsetSumToFind = (diff + sum) / 2; // Aditya Verma Equations xD.
// Use dynamic programming to count subsets with the desired sum
return countSubsetsWithGivenSum(arr, subsetSumToFind);
}
// Function to count subsets with a given sum using dynamic programming
public static int countSubsetsWithGivenSum(int[] arr, int sum) {
int n = arr.length;
int[][] dp = new int[n + 1][sum + 1];
// Initialize the base cases
for (int i = 0; i
for the case when the array has '0' then the answer will be differenent
Bhaiyya if they ask you to print that subsets then how to do??
use long long for target, totalSum, and the j, and yeah abs(S).
As already mentioned we need to take care of the case where 0's are present in the nums array and also one interesting corner which was left out.
Case 1) Zeroes in array.
For this we just need to make a small adjustment i.e include the base case 0 sum also which we were not including previously i.e. starting the column loop from 1. Now we need to start the column loop from 0 taking the 0 sum case also in consideration.
Modified loop =>
for (int i = 1 ; i < n+1 ; i++) {
for (int j = 0 ; j < sum+1 ; j++) {
if (arr[i-1] [100] and target = -100. For this we need to take care that our sum is always less that absolute value of target.
Modified code => if (sum < abs(target) || (target + sum) % 2 > 0) return 0;
I was stuck because of CASE 2 ( sum
Could you please explain the reasoning behind the corrective measures you took for case 1? How and why did taking j = 0 helps us resolve the problem? Thanks
@@HarshalDev You must understand what are these two loops for, these loops denote the states. i loop from 1 to n denote the number of elements I'm including in my sum calculation and j loop denote the target sum for those i elements ( a smaller sub problem of the orginal problem)
For eg consider I'm at i = 3, j = 5 transition in the table. So it means I'm considering a target sum sub/shorter problem where the there are 3 elements and Target sum to find is 5.
So when I start the loop from j = 0 instead of j=1 I'm taking into account the zero target sum sub problem too. Please let me know if it clears your doubt now..
if anyone facing some issue in leetcode question:
int s1 = (sum+target)/2; // if(sum < abs(target)) ==> sum + target will become negative and index issue hoga
if(s1 < 0){
s1 = (sum-target)/2; // if above problem, then we use the value of other subset .... simple
}
// Explanation
/*
s1 + s2 = sum
s1 - s2 = target
-----------------
2s1 = sum + target => s1 = (sum + target)/2 => CASE 1
2s2 = sum - target => s2 = (sum - target)/2 => CASE 2
*/
Use this as reference
bhaiya apka teaching mujhe acha lagta, bahut kuch shik raha hai . Mera ek request tha ki ek video placement preperation ke bare me kar saktha hai na, help hoga humko
God Level DP thnkss man ,Now we are actually think like How variable possible in Question
Sir ,the code is not giving correct result for all test case
amazing video. awesome explanation👏 one of the best on TH-cam