12 Target sum

[@Cool-ss7ph]

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

[@jiveshthreja1573]

An addition (sum+d > 0)

[@abhinavgupta6730]

Can you please explain the logic behind your third point. Thank you

[@solarsystem9156]

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

[@mdsaifhussainiqbal2236]

partition can be possible if sum is odd , partition will not be possible when (sum + d ) is odd

[@dakshveersinghchauhan6133]

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]

can u please explain the logic of all the above 3 points? I am a noobie in DP.

[@vrajpatel1877]

Thank you very much @dakshveersinghchauhan613

[@saurav1018]

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

[@amitrawat3004]

can u also explain his 3rd logic for arr with 0's why we r multiplying with power of its cnt@@saurav1018

[@bhavyapandey7404]

yar jab aap logic decode karte ho na, smile aa jati hai chehre par :)

[@ayushvats1808]

💯😂

[@euphoric3464]

Control bhai !!😄

[@rahulbairwa2705]

💪💯

[@prateeknanda4614]

Bhaiya kaha place hue?

[@swarnadipadhikary6809]

Sach me .... Ye wala qn meine pehle try kar raha tha +/- picking leke... Par jab logic dekha to😂😂

[@0anant0]

12 of 50 (24%) done! Nice revision on this one!

[@aryangautam7506]

where are you nowadays buddy?

[@Kanishq23]

lets see@@aryangautam7506

[@arpitakar3384]

1. smuggling cocaine 2. Directing XXX 3. Farmer 🪚 Protest 4. Dot net developer

[@UjjwalKumar-ss4uo]

We want similar playlist on trees and graphs . This playlist is pure gem

[@naganikhilbijjala1000]

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 🙏️🙏️

[@yash_renaissance_athlete]

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!

[@ankuragarwal4014]

can u tell that how u got submitted it to leetcode

[@TheAdityaVerma]

Glad it helped, Do share please !!

[@shyamjiwashcare]

@@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);

[@dheerjain2884]

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

[@snehithoddula7905]

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

[@shivampaliya9011]

After seeing this solun. I felt like "Rishta whi ,soch nai" xp

[@TheAdityaVerma]

ha bhai, gangadhar hi shaktimaan hai !! 😂😂

[@casual_chess]

@@TheAdityaVerma 🤣🤣🤣🤣

[@abhi6853]

@@TheAdityaVerma ha.. ha..

[@buzzfeedRED]

@@TheAdityaVerma bhai some tc are not working

[@MrLalit1313]

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.

[@tejaswarambhe7464]

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.

[@019_devarghachattapadhyay5]

what is the A,B,C problems? Could you please attach a link?

[@NewBIE-xz5jm]

@@019_devarghachattapadhyay5 bruh , those are contest problems A , B and C are like a way of sequencing its not anu name.

[@bidishaborgohain6373]

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

[@sarthakgaba1583]

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; }

[@AestroixCode]

Man, thanks a lot. I just found your comment and even I asked the same question. Thanks for improving the answer !

[@ArjunArjun-zg3mz]

This really helped!!

[@psthakur1199]

If we start the inner loop from j=0 instead of j=1 it automatically solves all the cases.

[@Colourshred]

@@psthakur1199 This is real DP solution if one understands why :')

[@alokyes]

@@psthakur1199 can you explain why that works

[@Sunny-ri4yo]

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.

[@TheAdityaVerma]

Will reach out to you soon in some free time. Till then keep watching !!

[@GarimaMahajan]

@@TheAdityaVerma i guess he is right, solving the question on leetcode i found a few things and constraints missing in your solution.

[@samirpaul2]

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]

[@anmolverma905]

@@samirpaul2 because we need to handle the cases where multiple zeroes are there in the array which increases the number of subsets

[@studyonline3236]

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]

[@adityapandey5264]

For Leetcode 494. Target Sum, we need to handle 2 more conditions:- if(sum < target) return 0; if((sum+target)

[@pinkkitty6553]

Thank you bhai

[@PraveenKumar-lf8cr]

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]

[@bhavyaagrawal7098]

but 1 condition still doesn't work if target =-200 and n=[100]

[@ashutoshbharti2082]

@@bhavyaagrawal7098 It should work, if(array_sum+d) array_sum: return 0 if (d + array_sum) % 2 != 0: return 0

[@honeyjha7217]

@@bhavyaagrawal7098 You need to take absolute value for target. so initially make target = abs(target), and then solve.

[@agrajgarg2831]

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

[@fardeenalam6929]

Hey dude can u explain why (target+totalSum)%2!=0, return 0 this condition is necessary.

[@kirtikhohal3313]

@@fardeenalam6929 See reasons for both the edge conditions are:- 1. sum

[@aman_axioms]

thanks man...now it got accepted on leet code

[@parasjain7118]

@@kirtikhohal3313 Thanks for your explanation ☺

[@anuritarawat8422]

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

[@aashimaa2681]

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]

[@vaibhavsharma8465]

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

[@janvisingla3746]

whenever i watch your video i am always like "WAAH KYA BAAT HAI" :)

[@AdityaSingh-zj1hv]

zero handle karne wala case ek baar dekhna padega keval Explanation Supeerrrrrrr se Upar!!

[@senseiAree]

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 ❤

[@PrashantKumar-gg5qd]

u thaught me most practical way of learning

[@TheAdityaVerma]

I am glad it helped you. Please share and help this channel grow !!

[@ShivamSahuIITP]

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

[@insaneclutchesyt948]

thank you mere bhai

[@pyarsingh353]

[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

[@nikhilmarabathula1760]

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 🙌

[@kiranrajpurohit7307]

o bhaiiii OP.....boom just a simple trick and problem solved .

[@asimvora544]

I never seen dp solving like this ,So Thanx for this videos.

[@x_rayapu3005]

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.

[@sakshamkankaria915]

the best dp lectures on yt frr

[@creatorstudio5945]

No doubt, this man has power that will make you fall in love with DP. - Ketan Sisodiya

[@gatecsementor]

Bro seriously I haven't seen anybody teach DP like this. You are awesome bro. Hats off bhai. Matlab maza hi aa gya

[@ambikasadhu4261]

the entire series helps in developing the right thought process. Thanks for your efforts!

[@programmerchoice1028]

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.

[@noobichesser9434]

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.

[@TheAdityaVerma]

Thanks mate ❤️

[@noobichesser9434]

@@TheAdityaVerma bhai Patreon pe message nahi dekha aapne.

[@agyaani8060]

Agreed💯❤

[@babumon5351]

You are a dynamic programming super star. (DPMan)

[@nishantgupta6902]

Thank you so much i recognized by myself....this problem is variation of count the number of subset with a given difference

[@vakhariyajay315]

Thank you very much. You are a genius.

[@shashwatrao6949]

Pura same ques bas confusion hi confusion create krta h problem setter Ab clr ho gya pura. Thank you sir

[@sandeepmandal9998]

Solved the question after understanding the problem statement and before watching the solution 😎

[@kaustubhnerurkar]

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

[@rishabsinha8749]

so return 0 for all those cases

[@nimishkhandelwal126]

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!

[@KashishMehndiratta]

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

[@darsisriguruaakash]

Aapke video be bahut achhe hai Bhai. mein aapka bhakt hun. Trees aapse seekha hai

[@pratyushbhatt1712]

Wow Dude!!, Again as far as I keep coming ahead, just continue to amaze me.!! KudoS!!

[@kaushalrajsinghbhati5076]

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.

[@Abhishek-Khelge]

Congratulations for 50k Subscribers

[@pushpendersharma673]

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.

[@Sushil_skp]

bhai sahab next level k concept diya ha bhaiya aap to

[@akshaysovani6052]

Awesome !! You are a really good teacher !! Excellent playlist.

[@rajubjc6349]

Wow, brilliant, however, I solved this as a tree. All thanks to you!!

[@nilaysheth3283]

How did you solve using trees ? Could you give your solution?

[@SnehaSingh-qz2kx]

amazing video. awesome explanation👏 one of the best on KZbin

[@ANKURSingh-yl2lj]

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!

[@kushagraofficial5347]

Your every single video is a masterpiece..

[@priyarathore9266]

Best DP course on internet!

[@sarcaastech]

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

[@veeracool875]

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 .

[@mahtabahmad1530]

sir can you please give a list of problems related to 0/1 knapsack other than these problems

[@Crosion1546]

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.

[@suvitsharma7432]

question ke baad : ye kya puuch liya ? ye kese hoga? after some time : ohh teri !!! aditya bhaiya OP !!!

[@shauryarehan4074]

Practical learning is the best !, kudos to your hardwork and way of teaching sir !

[@mrityunjayjaiswal3801]

i solved this que without seeing this video just becasue i watched previous videos. thanks a lot bro .

[@sidhantsuman4601]

maan gaye guru aapko macha diya bilkul sawal ko kaha se kaha pahucha diya

[@MacTavish2208]

Amazing dude

[@kms8320]

Now I am getting confidence in dp after watching your dp videos. Thanks bro, OP🔥

[@live_study_with_me]

Bhai bhai bilkul lit...

[@srieshagrawal2688]

Mind == blown when saw the correct logic GG!

[@harshagarwal6223]

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

[@ayush_walia]

same problem, tried solving this question in leetcode and got wrong answer. found any solution?

[@TheAdityaVerma]

Yeah, I check it 122/126 test cases are passing only, maybe I will upload a updated optimization for it soon !!

[@kuskargupt2887]

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

[@pratikkedar9979]

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

[@namanjain8779]

@@kuskargupt2887 i think it wont work as for input 010 output is 2

[@kumardivyanshu7327]

You are magician of DP.

[@abhigyanprakashjha3943]

Bhai ek number ek dm jiyo..jiyo bhai

[@TheAdityaVerma]

Shukriya Sir shukriyaa 😅

[@sumedharana4474]

I never thought DP could be this easy!!!! :-)

[@sachetwasti9369]

Very helpful lectures, thanks brother!!

[@tussharladdha4182]

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 ?

[@zangruver132]

MIND BLOWN 🤯

[@oqant0424]

the entire series helps in developing the right thought process

[@sheetallalwani1290]

Happy teacher's day to one who is teaching me dp in such a beautiful manner

[@easysolutions135]

Highest Quality content for DP

[@msk_bts]

This is amazing! Keep going Aditya!!

[@GateCSE280]

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?

[@tryingtomakesenseoftheverse]

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.

[@ravitiwari2160]

bhai u r great.. more power to you.. keep rocking

[@sharuk3545]

God Level DP thnkss man ,Now we are actually think like How variable possible in Question

[@bipinchandhdesa8686]

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

[@kapish4439]

Very well explained @Aditya Verma

[@vladimirputin2756]

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

[@vasuagrawal2954]

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

[@greenmug1058]

congrats 100k

[@TheAdityaVerma]

Thank you so much 😅

[@prakharsharma3974]

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]); }

[@fanigo138]

Next level! But interview ke wakt hidden question find nahi kar paunga mai... i guess bohot practice hi karni padegi

[@raghavendravernekar4103]

Great explanation!

[@hemantsood9579]

I always like these amazing videos by this amazing guy

[@aakashdev2478]

you are just awesome.. thanks for such good tutorials

[@baravkarnishithjagdish-iii5945]

bhai sahab man gaye aapko

[@chiragjaiswal9387]

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.

[@gauravruhela007]

Magnanimous!!!! Thanks a ton bhaiiiii

[@whatdfuck13]

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

[@ArunSethia]

awesome explanation

[@SamareshMaity231]

thank you sir kaafi maza aa raha hai...

[@hiteshusingh8571]

Very nice explanation!

[@himansh4812]

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

[@creationayush7399]

12 of 50 Done

[@vijaymittal810]

Can someone tell from where to practice different different problems(other then these 4) based on knapsack.

[@ayushman_sr]

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)