6.2 Sum Of Subsets Problem - Backtracking
ฝัง
- เผยแพร่เมื่อ 28 ส.ค. 2024
- Sum of Subsets problem
PATREON : www.patreon.co...
Courses on Udemy
================
Java Programming
www.udemy.com/...
Data Structures using C and C++
www.udemy.com/...
C++ Programming
www.udemy.com/...
![[LIVE] : ONE ลุมพินี 76 | คู่เอก "ผึ้งหลวง vs สมิงดำ"](http://i.ytimg.com/vi/9SBshmGQOIM/mqdefault.jpg)
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 😂😂
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 TH-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.
I have never come across a better teacher than you sir. Hats off!
The best teacher ever on TH-cam.
+1 vote!
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
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.
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
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 .
Just brilliant, it's a privilege to have a teacher like you.
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
thanks :) only suggestion is @ 6 : 40 it is 27 + 15 =42 ..
not many people can explain this well even though they understand inside out. You did a really good job!
Very helpful sir thank you.
Initially I thought your videos are too lengthy but now I realized your way of teaching is the best.
Best video professor, much hq quality, very nice kanimambo
the way of teaching is so unique. awesome content sir.
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.
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
1day before Sem
Real
Thankyou so much sir !!!!!
The way you explained was way more better than any teacher I've came across.
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.
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
You deserve all my respect sir , such a great teacher i wish you all the best
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 😂
I love Abdul so much ! The way he explains it , calm and cool !! He is a true Master Warrior of Programming !
I was just misunderstanding of something and by seeing this great video all confusions became clear, thank you
By far the best explanation Sir. Thank you very much.
It may be any tough sum,u make it easier by your explanation 😊
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
You explained it very well... This video helped me a lot...Thank you so much sir❤🙏
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!
Mashallah Sir aap ki class superb...Ur teaching mind-blowing sir 👍
Thanks for liking
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
what an explaination just outstanding thanku so much sir
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+.... .
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
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
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.
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
Tomorrow is my sem exam😂😂 just one video of this sir is enough to top DAA exam.
THANK YOU SIR❤❤❤
Sir u will get world's best teaching skills person🙏Award
Ye toh Abdul baari haii ye toh acha bacha haiii, ye duayein sunta haiii, achi baatein batata haii 💆🧘
Great explanation, good example and very easy to follow. I managed to implement and use this very quickly. Thanks a lot!
wonderful teaching sir thank u so much
Sir, pls give us code with this problem..
Great explanation, much better than my professor
This man is a savior.
NICE METHODS AND WAY OF TEACHING
Save me the day!! I will see you on Udemy
you re the real king, Abdul Bari
Sir, could you make coding videos of these algorithms as well? It would really help us:)
Thn...x for your explanation. Addition or discussion of time and space complexity will make you unique form others.
You take class awesome sir mainly this subset class sir i learn subset sir👌👌👌
Very well explained Abdul
THANK YOU SIR , YOUR EXPLAINATION WAS SO EXCELLENT
best explanation ever , thanks sir
Very nice sir thank you for helping us one day before our exam , you teach very well.
Alaguseriel
Azagu
Colaboren con este excelentísimo !
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 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.
Very informative lecture series for starting with Backtracking
Master of teaching😃
6:32 the given numbers are in descending order. Whats the point of adding 15 (next element )? Can somebody explain
I appreciate ur work sir. You are really amazing. .
Super explanation sir I hope this explanation will make all queries clear
at 6:35 ,, 27+15 = 42 not 43
😉
Sir ji dhnayaavad bot thanku apkaa. Iss sem ka Daa aap hi nikalonge mera😊
Excellent teaching 😎😎
Even our Daa Sir sent ur videos .don't know why they are getting salary which belongs to you .sir 😢
sir what is the time complexity for this problem? do we consider height as timecomplexity?
thank you so much, sir, your videos are really knowledgeable and helpful.
Thank you sir, I love your explaination😍 just one suggestion keep video time minimum for other video
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.
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?
Such simple and excellent explaination.
Honestly the best explanation ive found
Video cut at 5:34.
Sir outstanding explanation ... Sir really its easy to understand
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!!!
thanks sir i have cleared my backlogs
Very nice explanation sir
Thank you soo much for your Explanation sir
crisp and clear explaination
This man is a genius
Superb Explanation for this problem !
Thanks a lot sir.good explanation.
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
amazing explanation on this!
Amazing explanation! Thank you very much!
Excellent Teaching sir.Thank you
Watching these for the third time for my 2nd supplymentary
Thank you sir for good video lecture,I can understand easily
he : I am not the messiah
us: he is the messiah!
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)
Sir please make videos about other core computer science subjects
Thank you sir great explanation
My exam is today and watching this concept now 😂
sir once came to our college , when i was in second year , hope once agian he will come to for gest lecture on DAA
State-space tree is such an amazing tool. Why haven't I heard about it earlier?
nice explanation sir