Excellent sir I slept while my professor was teaching during my online classes but tomorrow I'm having my exam and I am watching your video's it was very helpful
beautifully explained, amazingly clear videography, easily understandable hand writing, simple examples, clear simple English speech so that everyone can understand, slow paced speech so that anyone can grasp the concept, clear audio and the best part is the calm attitude of explanation, just everything that is needed for a perfect explanation, your channel has it.
The way you are explaining the recursion (DFS) is the unique skill you have. I appreciate your time for making this video's. Hope this will helps many people.
because of your videos i study only one night before of exam ,you r making every student life very easy by just giving these all videos in free ,so thanks you sir .
This is an excellent explanation for the backtracking technique to solve this problem. An important precision about this approach, that is missing from the video and that may trip up or confuse the problem solver is that the *weights must be positive*. Without this precision, the bounding function doesn't make sense, since at the time we exceed the target sum during traversal, a later negative weight could bring it to target. So this backtracking approach works only if the weights are positive.
I don't go class because I know you will clear my all concept before exam. My teacher also made pdf from your lecture's screenshot. You are truly amazing. Sir
If I watched this as my last resource the day before having an exam, I wouldn't pass anything. It's good to take a first glance, or to break apart a problem and solve it, but not as an academic foundation. Step up your game, don't be lazy.
@@carlosgallegos1265well it depends on person to person. I'm used to studying on the last minute and UA-cam videos are my last resort if I don't understand anything from books and Abdul Bari has been like a God to me literally. I wasn't much into algos and I'm really interested to get into this more. The teachers we have are too underpaid and are not as qualified as well as don't have their concepts clear some of the times. Having a community online helps us help one another and get info quickly without looking into 100s of pages lol.
Thanks Abdul! Very clear walkthrough of backtracking! It helped me greatly. LOL at the inconsequential arithmetic mistake at 6:39! ;) just shows you're human!
Very good explanation. I had a little doubt, at 8:18 shouldn't it be greater than or equal to 'm' instead of greater than 'm' in 2nd bounding function. Eg if arr = [1,2,3] & sum = 6, then after including 1 ( [1,5] ), the 2nd bounding function will not let it go further (even though taking all elements would have generated the sum).
The 2nd bounding function is correct. It should be greater than m. You only apply the 2nd bounding function when descending down the right branch. When you descend down the right branch, it means that x[i]=0. In your example, after [1,5] and descending down the right branch x[2]=0 which means that 2 will not be included in the solution. The 2nd bounding function is telling you that you will not have enough values to reach the sum 'm' because the values going down the right branch will not be included in the solution. So for arr[1,2,3] and m=6, after taking 1 but not taking 2, you can't reach the value m=6.
No because if the rest of the weights can't add up to the number you are searching for then why continue? If the sum of your current sum plus the rest of the objects are less than that number then you'll never get it, so you stop.
The time complexity for this is still exponential. Consider the case where all of the elements are 1 and the last element is massive. If the target sum is less than the less element but more than all the other elements combined, no nodes are pruned
Very good video. I want to add an improvement to this backtracking. You can add another bonding function, if w array is sorted ascending so X_(i-1) < X_i < X_(i+1) then you know if adding X_i is already greater than m then you kill the node and it's brothers because X_i+1 > X_i
For benefit of everyone. Here is the manifestation of the concept in code: """ Identify all the subsets of a given set that will add upto a given target { 5, 10, 12, 13, 15, 18 }, 30 => [{5, 10, 15}, {5, 12, 13}, {12, 18}] """ from typing import List, Set def sumOfSubsets(nums: Set[int], target: int): def dfs(weights: Set[int]): if sum(weights) == target: output.append(list(weights)) other_weights = nums.difference(weights) # choose weights in an increasing order to avoid duplication of # results if len(weights) > 0: other_weights = [w for w in other_weights if w > max(weights)] for weight in other_weights: if sum(weights) + weight
A few questions I had: 1. Why don't we sort the array? 2. Does this not work for negative integers? 3. What is the complexity of this algorithm? 4. What if we have a list whose sum is 31? Won't that be a worst case scenario as we'll end up iterating through all 2^n possible paths and not find any solution?
Thank you so much sir for your videos it ws too good and the way your explaining the concepts are not complicated . It helped me a lot thank you once again.
sir, I have been looking for a good explanation for this problem using recursion since long. So far I found people directly starting with DP solutions where they create the DP table. That is just like mugging up. It is not intuitive at all. You can think of it after you have thought of a recursive solution. Atleast that's what I do. Thanks a lot for making this video. You made my day!
The left part of the node is the sum of all the x you included until now but the right part is the sum of all the remaining x you can add, so the right part changes repeatedly no matter if you include the particular x or not. So when x4 is excluded, the remaining choices you have are just x5 and x6, so sum would be x5 + x6 = 15+18 = 33 not 46. So think of the right part as something that has the sum of the remaining elements after a level you're at. At level x2, the values is x3+x4+.... and at x3 it is x4+x5+.... .
Thanks for the wonderful videos and It would be really helpful if you include writing code for this kind of DP, Back tracking Problems. May be, by watching your code, most people may get essence of "how to write code" for this kind of problems. My request is to include code for at least one problem of such type as including for all will be hectic.
Sir, the way you explain is actually great (it clears the concepts well). But I have a question, how to implement these solutions in a program, how to code these strategies with an efficient implementation. It would be very kind of you if you attach a link in the description (or make some more videos) stating the codes and what's the idea behind its efficient implementation. Thanks in advance....!!!
To understand the algorithm your videos are awesome. But I would suggest if you could please add the pseudocode at least while explaining the algorithm it would been more helpful.
Excellent sir I slept while my professor was teaching during my online classes but tomorrow I'm having my exam and I am watching your video's it was very helpful
👍🏻👍🏻
Same bro, hope you scored good in your exam
@@srujangurram yeah bro I scored 80 percent in my sem end examination
@@monishpidugu5134 that's awesome ! we have exam tomorrow. hope i does well too 🤞
I read I slept with my professor 🤣
beautifully explained, amazingly clear videography, easily understandable hand writing, simple examples, clear simple English speech so that everyone can understand, slow paced speech so that anyone can grasp the concept, clear audio and the best part is the calm attitude of explanation, just everything that is needed for a perfect explanation, your channel has it.
Even my professor watches ur videos!
If she forgets something we say her video is buffering 😂😂
My Professor Watches too but shortly explains algorithm 😂
You got me at "buffering" 😂😂
@@anupriyaranjan8966 Mam aap yaha 😄😀😄😀😄
DEAD
Possibly you will get the same question in the exam 😂😂
I have never come across a better teacher than you sir. Hats off!
The best teacher ever on UA-cam.
+1 vote!
You are such an amazing teacher; everything you explain is understood by me at once, and I am not even a meritorious student lol...
thank you
The way you are explaining the recursion (DFS) is the unique skill you have. I appreciate your time for making this video's. Hope this will helps many people.
does not sound like a compliment
@@kurru_kamiz3458why?it did sound like one
Just brilliant, it's a privilege to have a teacher like you.
because of your videos i study only one night before of exam ,you r making every student life very easy by just giving these all videos in free ,so thanks you sir .
This is an excellent explanation for the backtracking technique to solve this problem. An important precision about this approach, that is missing from the video and that may trip up or confuse the problem solver is that the *weights must be positive*. Without this precision, the bounding function doesn't make sense, since at the time we exceed the target sum during traversal, a later negative weight could bring it to target. So this backtracking approach works only if the weights are positive.
thanks :) only suggestion is @ 6 : 40 it is 27 + 15 =42 ..
I don't go class because I know you will clear my all concept before exam. My teacher also made pdf from your lecture's screenshot. You are truly amazing. Sir
Best video professor, much hq quality, very nice kanimambo
not many people can explain this well even though they understand inside out. You did a really good job!
content is good...including pseudocode explaination would be really helpful
+1
Sir have already explained how to solve the problem. Now it's your task of solving the whole problem.
Hit like if you have exams tomorrow and are watching this for end semester.
yes
yes bro
Hit like i have exam today 😂😂😂😂
If I watched this as my last resource the day before having an exam, I wouldn't pass anything. It's good to take a first glance, or to break apart a problem and solve it, but not as an academic foundation.
Step up your game, don't be lazy.
@@carlosgallegos1265well it depends on person to person. I'm used to studying on the last minute and UA-cam videos are my last resort if I don't understand anything from books and Abdul Bari has been like a God to me literally. I wasn't much into algos and I'm really interested to get into this more. The teachers we have are too underpaid and are not as qualified as well as don't have their concepts clear some of the times. Having a community online helps us help one another and get info quickly without looking into 100s of pages lol.
Tomorrow is my sem exam😂😂 just one video of this sir is enough to top DAA exam.
THANK YOU SIR❤❤❤
the way of teaching is so unique. awesome content sir.
Very helpful sir thank you.
Initially I thought your videos are too lengthy but now I realized your way of teaching is the best.
Thanks Abdul! Very clear walkthrough of backtracking! It helped me greatly. LOL at the inconsequential arithmetic mistake at 6:39! ;) just shows you're human!
I also notice.
yeah, noticed as well :D
Very good explanation. I had a little doubt, at 8:18 shouldn't it be greater than or equal to 'm' instead of greater than 'm' in 2nd bounding function. Eg if arr = [1,2,3] & sum = 6, then after including 1 ( [1,5] ), the 2nd bounding function will not let it go further (even though taking all elements would have generated the sum).
Yeah, It seems so. Should have been ≥ m.
The 2nd bounding function is correct. It should be greater than m. You only apply the 2nd bounding function when descending down the right branch. When you descend down the right branch, it means that x[i]=0. In your example, after [1,5] and descending down the right branch x[2]=0 which means that 2 will not be included in the solution. The 2nd bounding function is telling you that you will not have enough values to reach the sum 'm' because the values going down the right branch will not be included in the solution. So for arr[1,2,3] and m=6, after taking 1 but not taking 2, you can't reach the value m=6.
No because if the rest of the weights can't add up to the number you are searching for then why continue? If the sum of your current sum plus the rest of the objects are less than that number then you'll never get it, so you stop.
The time complexity for this is still exponential. Consider the case where all of the elements are 1 and the last element is massive. If the target sum is less than the less element but more than all the other elements combined, no nodes are pruned
See the second bounding condition, if the considered weight + total remaining weight is less than target sum, then no need to search further
At first call, your example will be terminated
Very good video. I want to add an improvement to this backtracking. You can add another bonding function, if w array is sorted ascending so X_(i-1) < X_i < X_(i+1) then you know if adding X_i is already greater than m then you kill the node and it's brothers because X_i+1 > X_i
But sorting also takes some time O(nlogn) and here you are taking time to reduce time, which is meaningless
Seriously ... my professor given same example...I think she watches ur vedios 😂😂😂😅
Same 😅😅😅
Oh yeah, *Vedio.*
Same here also
Ya same here..even my professor gave the same example🤭
Same 😂
You deserve all my respect sir , such a great teacher i wish you all the best
I love Abdul so much ! The way he explains it , calm and cool !! He is a true Master Warrior of Programming !
By far the best explanation Sir. Thank you very much.
1day before Sem
Real
Thankyou so much sir !!!!!
The way you explained was way more better than any teacher I've came across.
For benefit of everyone. Here is the manifestation of the concept in code:
"""
Identify all the subsets of a given set that will
add upto a given target
{ 5, 10, 12, 13, 15, 18 }, 30 => [{5, 10, 15}, {5, 12, 13}, {12, 18}]
"""
from typing import List, Set
def sumOfSubsets(nums: Set[int], target: int):
def dfs(weights: Set[int]):
if sum(weights) == target:
output.append(list(weights))
other_weights = nums.difference(weights)
# choose weights in an increasing order to avoid duplication of
# results
if len(weights) > 0:
other_weights = [w for w in other_weights if w > max(weights)]
for weight in other_weights:
if sum(weights) + weight
what an explaination just outstanding thanku so much sir
Mashallah Sir aap ki class superb...Ur teaching mind-blowing sir 👍
Thanks for liking
I was just misunderstanding of something and by seeing this great video all confusions became clear, thank you
It may be any tough sum,u make it easier by your explanation 😊
You explained it very well... This video helped me a lot...Thank you so much sir❤🙏
Tq u sir it is very useful me because tmr my daa exam tq u so much it is one of the my dout how to solve this but now i know how to subsititute
Just saw this video on morning of my sem exam for 4 min ,dayumm just helped a lot ,didn't expect they would ask this. Guess im so lucky afterall
A few questions I had:
1. Why don't we sort the array?
2. Does this not work for negative integers?
3. What is the complexity of this algorithm?
4. What if we have a list whose sum is 31? Won't that be a worst case scenario as we'll end up iterating through all 2^n possible paths and not find any solution?
Thank you so much sir for your videos it ws too good and the way your explaining the concepts are not complicated . It helped me a lot thank you once again.
wonderful teaching sir thank u so much
sir, I have been looking for a good explanation for this problem using recursion since long. So far I found people directly starting with DP solutions where they create the DP table. That is just like mugging up. It is not intuitive at all. You can think of it after you have thought of a recursive solution. Atleast that's what I do. Thanks a lot for making this video. You made my day!
How can the value of m remain 33 when we not including 4th object ie x4=0 i think the ans 27,46. correct me if im wrong
Yes bro u are right. That's why i come to the comment section. I am sure any one student are done comment on this silly mistake.
He does the same at 27,18 idk i think that is how you do it.
He is just taking track of remaining weight to become 0, that's why he is decreasing regardless of including or excluding the element
The left part of the node is the sum of all the x you included until now but the right part is the sum of all the remaining x you can add, so the right part changes repeatedly no matter if you include the particular x or not. So when x4 is excluded, the remaining choices you have are just x5 and x6, so sum would be x5 + x6 = 15+18 = 33 not 46. So think of the right part as something that has the sum of the remaining elements after a level you're at. At level x2, the values is x3+x4+.... and at x3 it is x4+x5+.... .
This man is a savior.
Sir u will get world's best teaching skills person🙏Award
Great explanation, good example and very easy to follow. I managed to implement and use this very quickly. Thanks a lot!
NICE METHODS AND WAY OF TEACHING
You take class awesome sir mainly this subset class sir i learn subset sir👌👌👌
Great explanation, much better than my professor
Master of teaching😃
Save me the day!! I will see you on Udemy
you re the real king, Abdul Bari
Ye toh Abdul baari haii ye toh acha bacha haiii, ye duayein sunta haiii, achi baatein batata haii 💆🧘
at 6:35 ,, 27+15 = 42 not 43
😉
Excellent teaching 😎😎
best explanation ever , thanks sir
Very well explained Abdul
Sir, could you make coding videos of these algorithms as well? It would really help us:)
I appreciate ur work sir. You are really amazing. .
Super explanation sir I hope this explanation will make all queries clear
Colaboren con este excelentísimo !
Thn...x for your explanation. Addition or discussion of time and space complexity will make you unique form others.
Very nice explanation sir
Very informative lecture series for starting with Backtracking
THANK YOU SIR , YOUR EXPLAINATION WAS SO EXCELLENT
Thanks for the wonderful videos and It would be really helpful if you include writing code for this kind of DP, Back tracking Problems. May be, by watching your code, most people may get essence of "how to write code" for this kind of problems. My request is to include code for at least one problem of such type as including for all will be hectic.
Sir, pls give us code with this problem..
Sir outstanding explanation ... Sir really its easy to understand
he : I am not the messiah
us: he is the messiah!
Very nice sir thank you for helping us one day before our exam , you teach very well.
Alaguseriel
Azagu
Sir ji dhnayaavad bot thanku apkaa. Iss sem ka Daa aap hi nikalonge mera😊
Such simple and excellent explaination.
Honestly the best explanation ive found
how many of you are watchin 1.5x or 2x hit like here
kabi kabhi nhi hamesha lagta hai ki sir ich bhagwan hai.... akash gaytunde
watching at 2.5x
bro u raking likes for same comment in every vid lmao
amazing explanation on this!
nice explanation sir
Sir, the way you explain is actually great (it clears the concepts well). But I have a question, how to implement these solutions in a program, how to code these strategies with an efficient implementation. It would be very kind of you if you attach a link in the description (or make some more videos) stating the codes and what's the idea behind its efficient implementation. Thanks in advance....!!!
Thanks a lot sir.good explanation.
python code::
l1=[5 , 10 , 12 , 13 , 15 , 18]
tot_sum=0
for l in l1:
tot_sum+=l
weight_sum=0
m=30
sol=0
def backtrack(weights , index , weight_sum , tot_sum):
global sol,m
print(weights , index , weight_sum , tot_sum)
if weight_sum==m:
print("yess")
sol+=1
return
if weight_sum>m:
return
if index>=len(weights):
return
backtrack(weights , index+1 , weight_sum+weights[index] , tot_sum-weights[index])
backtrack(weights , index+1 , weight_sum , tot_sum-weights[index])
backtrack(l1 , 0 , 0 , tot_sum)
print(sol)
crisp and clear explaination
thank you so much, sir, your videos are really knowledgeable and helpful.
This man is a genius
sir what is the time complexity for this problem? do we consider height as timecomplexity?
Watching these for the third time for my 2nd supplymentary
thanks sir i have cleared my backlogs
Excellent work..
6:32 the given numbers are in descending order. Whats the point of adding 15 (next element )? Can somebody explain
wow !! so intelligent lecture !! sir
Thank you sir, I love your explaination😍 just one suggestion keep video time minimum for other video
Thank you sir for good video lecture,I can understand easily
To understand the algorithm your videos are awesome. But I would suggest if you could please add the pseudocode at least while explaining the algorithm it would been more helpful.
Excellent Teaching sir.Thank you
Even our Daa Sir sent ur videos .don't know why they are getting salary which belongs to you .sir 😢
everyone is gangsta untill a real gangsta walk in ..
Ganga 😂😂
At 6.17 when we are excluding 4th node then why we are using sum that come when we include the 4th node?
I do have the same doubt ma'am
I know right!!!
Superb Explanation for this problem !
professor of professors!!!
I have a doubt on that we did not include some items so that y u reduce the total weight from where we did not consider that item
My exam is today and watching this concept now 😂
Video cut at 5:34.
State-space tree is such an amazing tool. Why haven't I heard about it earlier?