L6. Recursion on Subsequences | Printing Subsequences

Рет қаралды 538,655

2 жыл бұрын

Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- Please check out the entire channel for other sets of series on tougher and complex topics. Also do consider subscribing :)
Please check out the SDE sheet which the entire country is using and getting placed at top-notch companies: takeuforward.org/interviews/s...
Checkout Striver's Handles: linktr.ee/takeUforward

Пікірлер: 510

@jaimitkumarpanchal7603 Жыл бұрын

Man i usually don't comment on KZfaq videos, but i just solved 3 medium level questions in under 20 mins. Damnnnnnnn i have no words to express. but this video specifically is a gem to solve most of the recursion sub-seq problem. Thank you so much 😄 Edit : i have watched this video 2-3 months back(December) for dynamic programming, till this day i remember every detail of the video.

@mrsmurf911 Жыл бұрын

from sklearn.pipeline import Pipeline import sklearn.svm from sklearn.linear_model import LogisticRegression knn=KNeighborsClassifier(n_neighbors=8) rfc=RandomForestClassifier(max_features=2,n_estimators=64,bootstrap=False,oob_score=False) svm = svm.SVC(kernel='rbf',C=1,gamma=1) lr=LogisticRegression(C=0.01,max_iter=100,penalty='l2') # define the pipeline # define the pipeline pipe = Pipeline([ ('scaler', StandardScaler()), ('knn', knn), ('rfc', rfc), ('svm', svm), ('lr', lr), ('preds', FunctionTransformer(lambda x: x.predict_proba(x)[:,1].reshape(-1,1))) ]) # fit the pipeline to your data pipe.fit(X_train, y_train) # predict on new data y_pred = pipe.predict(X_test) # evaluate the pipeline's performance accuracy = pipe.score(X_test, y_test)

@ashwanisharma8903 2 жыл бұрын

Best thing is you have very deep understanding of the topics and you code your own way. While other videos mostly pick code from GFG and explain which goes above head. Thanks for lovely explanation.

@jaibhagat7441 Жыл бұрын

Huh

@aeroabrar_31 Жыл бұрын

The code for printing string subsequences. package Recursion_2; import java.util.ArrayList; public class Subsequences { public static void main(String[] args) { String s="abcd"; char[] c=s.toCharArray(); print_string_subseq(new ArrayList(),0,c,s.length()); } public static void print_string_subseq(ArrayList al,int ind,char[] c,int n) { if(ind>=n) { if(al.size()==0) System.out.print("{}"); for(char t:al) { System.out.print(t); } System.out.println(); return; } print_string_subseq(al,ind+1,c,n); al.add(c[ind]); print_string_subseq(al,ind+1,c,n); al.remove(al.size()-1); } } Output : {} d c cd b bd bc bcd a ad ac acd ab abd abc abcd

@roshangeorge97 7 ай бұрын

He is unique XD

@sanjayhazra181 2 ай бұрын

Yup, also some just mug up from chatgpt and code .

@sarathchandra941 2 жыл бұрын

Finally, the day has come to understand and as well code for the same.

@ashutoshthite 2 жыл бұрын

💯💯

@ShubhamKumar-nr9ug Жыл бұрын

JAVA CODE FOR THE SAME WILL BE ::- public static void main(String[] args) { int[] arr = { 3, 1, 2 }; ArrayList list = new ArrayList(); printSub(0, arr, list); } private static void printSub(int i, int[] arr, ArrayList list) { if (i == arr.length) { System.out.println(list.toString()); return; } list.add(arr[i]); printSub(i + 1, arr, list); list.remove(list.size() - 1); printSub(i + 1, arr, list); }

@badboybb519 Жыл бұрын

It helped me a lot bro

@klakshmisuryateja8320 Жыл бұрын

Very helpful

@pehdntene6473 3 ай бұрын

I do not understand one thing if we try to apply the same logic but when the return type is List this doesn't work cause instead we get an empty list when i == arr.length

@dgvj Жыл бұрын

Best series on recursion in the internet. Thanks alot for your time and effort.

@jayeshbangar8373 Жыл бұрын

JAVA Code- public static void sub(ArrayList al, int arr[], int i){ if(i == arr.length){ System.out.println(al.toString()); return; } al.add(arr[i]); sub(al,arr,i+1); al.remove(al.size()-1); sub(al,arr,i+1); }

@jatinlanje5741 Жыл бұрын

with small correction public static void sub(ArrayList list, int arr[], int i){ if(i == arr.length){ if(list.size()>0){ System.out.println(list.toString()); } return; } list.add(arr[i]); sub(list,arr,i+1); list.remove(list.size()-1); sub(list,arr,i+1); }

@mayankshukla7195 7 ай бұрын

thanku so much brother

@travelnlearn Жыл бұрын

THANK YOU BRO, BEST PART: YOU COmpletely connects with your audience and each and every step goes direclty into our brain and we understand everything. Thank You & keep it up

@potatocoder5090 2 жыл бұрын

Brilliant explanation! I never quite understood this question before watching this video. The take/not take pattern is going to be in my head forever. Thank you so much! You're an amazing teacher :)

@yotowilliam5465 Жыл бұрын

Amazed by your lessons, i feel like i know recursion better than before, thanks bro.

@samsmith3961 Жыл бұрын

this has been beautifully explained ..I've been searching for this explanation for hours now and this was good

@sureshgarine 2 жыл бұрын

indeed, it's a wonderful explanation. thanks for taking time and doing this for community

@adityadeshbhartar7172 10 ай бұрын

What a explaition strting from base case to dry run to recursion tree , Fully fantastic, even i used to code in java still noone can reach your level of explanation ❤🤘 Best video...

@tharundharmaraj9045 Жыл бұрын

Simple english....No confusions......... Great work

@udaykulkarni5639 Жыл бұрын

Man! This is crazzyyyy!! I never really comment on KZfaq. But this is some next level shit ! I kept memorizing the subseq code as I was sure i would never understand this. But you have finally made it clear and I dont need to memorize it ! Its pretty straight forward! Thanks a ton😊❤

@soumyajeetsengupta3064 2 жыл бұрын

I have seen soo many videos for this problem and never understood anything but your explanation it was awesome it gave me confidence to solve any problem of this kind(take or not take). Thankyou Striver sir!

@ShubhamKumar-sj6dp Жыл бұрын

or it could be opposite , since you tried it many times , this was the time it clicked , it would have been same if you would have watched this video first and other video would have clicked !!!!!!

@studynewthings1727 10 ай бұрын

Thankyou STRIVER, for explaining the subsequence problem in a awesome manner.

@ardhidattatreyavarma5337 Жыл бұрын

after this video I solved subset sum pretty easily. Thank for your crystal clear explanation

@AngadSingh97 2 күн бұрын

Excellent explanation, itni baar dekhne ke baad it is even possible to watch at 3x and revise easily, which is amazing.

@ayushuniyal2586 Жыл бұрын

after watching many videos on recursion ,i was not able to do dry run of recursion question .Now i can say this is the best explaination for begineers to do dry run and understand recursion.just fantastic bhaiya like how easy you explained .hats off nailed it respect++.

@ujjwalshrivastava3594 Жыл бұрын

How to learn recursion?

@ashokdurunde1814 2 жыл бұрын

Thank you so much! You're an amazing teacher :)

@sojwalgosavi4406 Жыл бұрын

You are taking great efforts and we are learning from you Striver.

@visheshwaghmare7504 Жыл бұрын

If we want to avoid the remove part, we can first call without adding and then add the element and call function again with the added element in the vector.

@amit2194 Жыл бұрын

if you want to remember it like using " take " and "not take " you should follow that

@aviral1430 Жыл бұрын

Power Set by Striver : kzfaq.info/get/bejne/mJ1xjMWhspu9onk.html

@aravinda1595 Жыл бұрын

Thanks a lot sir,I have been frustrated since a long time because of recursion ,it felt impossible for me to solve any leetcode problem but after your series i feel more confident in approaching any backtracking problem.You just don't explain a solution for a particular problem but a solution which can be modified and used for any other similar problem.

@ujjwalshrivastava3594 Жыл бұрын

Bro how u understand recursion?

@abishekbaiju1705 2 ай бұрын

I watched it once didn't understand, but after that watched again by following him with a pen and paper and understood completely.

@jitendrakumar-vv8ho 9 ай бұрын

it was quite difficult to understand

@PIYUSHTAILORstillalive Ай бұрын

no problem. [] and arr[] are different and need to be passed through the recursion.In the explanation it might have confused.

@pranayramteke2848 10 күн бұрын

Do the dry run buddy, recursion is all about stack tracing and tree tracing 9:50

@jitendrakumar-vv8ho 10 күн бұрын

@@pranayramteke2848 thanks for your advice buddy but internship season is going on and i am unable to solve questions in OA round can you help ???

@habeeblaimusa4466 Жыл бұрын

I had to watch this video for more than 5 times. God bless you bro

@RishabhJain-iz5xk 2 жыл бұрын

HANDS DOWN BEST EXPLANATION ON INTERNET!

@SuperWhatusername 2 жыл бұрын

Earlier I was learning recursion and dynamic programming together and that was my mistake. Thanks for creating this playlist and awesome explanation.

@azaanakhtar1974 2 жыл бұрын

Uh are write in which language Cpp Or java

@azaanakhtar1974 2 жыл бұрын

I wrote in java bt i faced an error working with array and list

@SuperWhatusername 2 жыл бұрын

@@azaanakhtar1974 CPP

@ratanmasanta3210 2 жыл бұрын

@@azaanakhtar1974 Try this: static void findSubsequence(int index, int[] array, ArrayList arrayList) { if(index == array.length) { System.out.println(Arrays.toString(arrayList.toArray())); return; } arrayList.add(array[index]); findSubsequence(index+1, array, arrayList); arrayList.remove(arrayList.size() - 1); //need to remove last element findSubsequence(index+1, array, arrayList); }

@azaanakhtar1974 2 жыл бұрын

@@ratanmasanta3210 thanks buddy

@ryanmathew6397 10 ай бұрын

That really was one of the best way to explain sub-sequence.

@gwalaniarun 2 жыл бұрын

Awesome man, love your explainatiton.

@sumanthvarmakarampudi7251 Жыл бұрын

Super Clear, Great Effort Always thankful to you sir

@factsmotivation7728 Жыл бұрын

Thanks you so much sir for this wonderful content ,i loved with recursion sir 🙏🙏

@vvssreddy903 19 күн бұрын

I have a small doubt, during 3rd recursive call the list is [3,2,1] and i value is 3. Now as i= arr.length, we print the list. After that to back track, we remove recently added element which is 2. Now the list becomes [3,1] but the i value doesnt change. It remains same 3.and after removing, we did sub(al,arr,i+1) which is sub([3,1],arr,4).im confusing here

@Codebond7 Жыл бұрын

Understood. will complete recursion today no matter how much time it takes.

@soorma7869 Жыл бұрын

Finally it's crystal clear... After watching this video 3-4 times

@anshvashisht8519 Жыл бұрын

thank you so much for the recursive tree it helped a lot

@aashapun6533 2 жыл бұрын

Thank you so much. Worthy Content!!

@sadmanmehedisivan6581 2 жыл бұрын

It will be so cool if you can add the codes in the description!

@omkarwarule5483 10 ай бұрын

one of the beautiful play list for recursion on you tube

@sreenandini766 2 жыл бұрын

Super explanation sir .Thank you so much❤️

@laginenisailendra1959 Жыл бұрын

May God bless you with all the health and wealth you need. I understood it.

@Cool96267 2 жыл бұрын

Hey Striver, Could you also please attach the link of the respective leetcode questions?

@preetiipriya 2 жыл бұрын

found?

@Dheeraj-ed6rr 2 жыл бұрын

@@preetiipriya Leetcode 78

@akshanshsharma6025 Жыл бұрын

@@Dheeraj-ed6rr thanku bro

@chandan1929 2 жыл бұрын

if I don't pass the vector &ds as reference then I don't have the need to ds.pop_back() correct ??

@takeUforward 2 жыл бұрын

Then it creates a new copy everytime, which will lead to tle :(

@Ayushkumar-co9mc 19 күн бұрын

Thanks a lot sir, now its crystal clear i made 2-3 recursion trees by my own it took me an hour but now its very clear.

@arnabkundu1648 23 күн бұрын

I have understood it extremely well. Thank you sir.

@parthsalat 2 жыл бұрын

Thanks a lot for this priceless video!

@shivalikagupta3433 2 жыл бұрын

Thank you!!! Extremely wonderful!!!

@takeUforward 2 жыл бұрын

You're very welcome!

@keertilata20 2 жыл бұрын

loved it, thank you so much :)

@ritvi5717 2 жыл бұрын

amazing teacher thank you so much :)

@vinnuhary2198 3 ай бұрын

mad respect to this man for keeping it super simple

@puranjanprithu6337 2 жыл бұрын

the tree simplified everything...thanks man

@akshaybhagwat6179 2 жыл бұрын

The best explanation ever exist on the youtube.

@Highlights_Point Жыл бұрын

Great Explanation sir i feel the recursion today

@sumitvishwkarma6907 Жыл бұрын

Now I understand this subsequence, after watching famous courses of CN, CB, I don't understand from them that deeply

@soorajsridhar3279 Жыл бұрын

Man this was an amazing way of explaining!!!!!!!!!!!!!!!!! l

@ankitbhatt5630 2 жыл бұрын

Really good explanation !

@roliagrawal3124 11 ай бұрын

Explanation was good but have one question though why we need to create res.add(new ArrayList(ans)); everytime new arralist?

@nahidfaraji5069 Жыл бұрын

No one can beat this Explanation.

@sriramrajkumar2774 5 ай бұрын

Anyone clear me this doubt. At 22.38 striver changed not pick first then picked second i thing the pop_back is not necessary. Am i correct?

@straightfacts5683 5 ай бұрын

i have same doubt couldnt understand that

@sharmakartikeya 2 жыл бұрын

Just don't stop uploading anytime you feel you are not getting enough views. Good Luck.

@radharamamohanakunnattur3035 Жыл бұрын

Understood!! Awesome explanation!!

@siddartha1328 Жыл бұрын

It's just amazing what an explanation.

@devaciustheoneaboveall1389 Жыл бұрын

hey!! Quick question why do we need to have f(i+1, arr[]) after removing the last element we added? cause the value of index is already 3 right . So, wouldn't it work with f(i, arr[]) ????

@thegamingschool9509 Жыл бұрын

yes because when you do i+1 it will only increment inside that called function but outsite the function it is still 2

@consistency_Is_key Жыл бұрын

watched it 4 times to understand this above 80% ,nice

@purushottamkumar3140 Жыл бұрын

Hats'Off to this Guy. Amazing

@user-sz1rm7bj7r 5 ай бұрын

Amazing, lost for words 👏🏽👏🏽👏🏽

@pritishpattnaik4674 2 жыл бұрын

Beautifully explained

@radhikagujral3435 5 күн бұрын

can someone explain when we reach i=3 and go back the array becomes [31] but wasnt i=3 already so shouldnt it change to i= 4

@Learner010 2 жыл бұрын

first time I understand this. Thanks bro

@anishmishra4988 11 ай бұрын

I have a little curious question that why to remove them later why not first make the recursive call without taking the element and then later add it then made the recursive call ? If Order is not Important of the sub-sequences.

@niitteenpathak5620 Жыл бұрын

Thank you so much for amazing explanation.

@bazeer1498 Жыл бұрын

after watching 5 times with paralally coding ..now i finally understand the whole concept of take and not take lol😆

@MindMunchies. Жыл бұрын

Thanks striver After watching it from all the tutors on youtube Finally i conclude you are a true gem 🤍 bro... will definitely meet you one day insha allah

@lastminutegyan9975 8 ай бұрын

Hi Striver, I am watching your recursion video from starting, Now I know how recursion works but how to make recursive function is what I didn't get. I understood the concept but after looking at some random question how I gonna make recursive call that I ddn't understand. I will be completing this series and hope by the end I know to make recursive function.

@rishabhkumartiwari7992 10 ай бұрын

what if i want to add to a list and return that lis which contains all the subsequence which removing step occurs it also removes from that list

@swaroopkv4540 Жыл бұрын

If we want to add subsequence inside another array what to do?

@SaketAnandPage 7 күн бұрын

Can we call just before addition and after addition? Why are we removing it?

@Yash-uk8ib 2 жыл бұрын

Sir, i can understand that i==n will be a base case but i>n will not happen.. as soon as i reaches n, it will return. I>=n is not making any sense to me. Correct me if I am wrong!!

@yashverma2986 2 жыл бұрын

Ha shi h tu bhi i==n hi shi h

@shauryatuli2241 2 жыл бұрын

I had the same doubt but I think the idea is i>= n (already contains i == n ) , the greater than sign is for extra precaution I guess or maybe because Bhaiya from the starting is teaching i>= n , in all his previous video ... maybe he want to show continuity in his code and teaching style

@Yash-uk8ib 2 жыл бұрын

@@shauryatuli2241 ok

@nikhilnaroliya3958 Жыл бұрын

Love the way you explained 💯💥

@user-ok4fx3kl6f 9 ай бұрын

so if I understood it right, because list is a mutable data structure, we have to do the remove step so that we can get back our original list. Is that right ?

@sujalsamai6459 2 жыл бұрын

So useful video. Thanks 👍🙏

@nishant0072008 Жыл бұрын

pls do complete dry run, i hope you understand it becomes more complex as you move forward, and that is where it becomes difficult to understand.Thanks

@Codewithwaseem 2 жыл бұрын

Awesome explanation, understood!

@ElonMusk-ez5xz 2 жыл бұрын

So this comes under parameterized recursion correct?

@joeyaintwaffling 2 жыл бұрын

Aur tarakki mile aapko bhai, kya samjhate ho

@horccruxxxop4184 2 жыл бұрын

Hello bhai. 12:07 pr when we had popped 2 then it can to next line where ind+1 should be done but you had passed 3 why??

@treedash1653 2 жыл бұрын

Hii striver! I've been learning recursion since the last 2 months, but i am still facing problems bro, i can't "Think" in the recursive way, like i can't approach a problem with recursion in mind, how should I learn the way of thinking? I've been practicing but no progress, should I just leave recursion and focus on other algorithms without recursion? (I'm in my 4th sem)

@prasunkumar1434 2 жыл бұрын

all recursive solutions can be done using iteration but the vice versa is not true.

@unknownuser8912 2 жыл бұрын

look if you have already given recursion more than 1 month , I think you should move forward now because when you will learn trees graphs and dp it will strengthen your recursion . This happens with most of the coders so just move forward and keep learning .

@treedash1653 2 жыл бұрын

@@unknownuser8912 I have skipped graph for this year, will learn that after getting a bit better in CP. Is it wrong? Should I learn it now?

@unknownuser8912 2 жыл бұрын

@@treedash1653 skipping graph for focusing on cp is okay but make sure once you feel comfortable with cp ,you are completing graph , as it is one of big3's(tree,dp and graph) .Also you will require knowledge of graphs when you reach expert .

@RahulGupta-dc1su 5 ай бұрын

Hey , what if call recursion call for not including the element before addition function call, the I think , there is no need to remove the element .

@savita6670 Жыл бұрын

Amazing explanation, can we reduce time complxity

@namitvarshney2142 2 жыл бұрын

Can anyone explain me? For example in case of array of size 3. The time complexity will be 2^n * n that will be 24. But if we count the the number of calls then in this particular case their are total 14 calls, so the actual Time complexity should be 14 (calls) + 8(for loop for printing) = 22 and if you see for larger test cases size the difference would be greater.

@VasheshJ 2 жыл бұрын

It's kinda like bubble sort's time complexity. It will never reach the worst case but you have to account for the worst possible time complexity.

@subhadipmaity3253 2 жыл бұрын

Nice Explanation, Thank You

@tee_vee1121 2 жыл бұрын

at 11:48 why it removed arr[2] and not arr[3] because the last index was 3 ?

@pratyushvaibhav Жыл бұрын

Watched the intermediate few minutes thrice and finally understood , lesson I learn't : sometime we need a small self-upgradation to understand the educator , not always the teacher(educator) is bad .

@abdulshahid7173 2 жыл бұрын

What's difference between this and subset video in ur Playlist can you please explain

@simransimran6766 Жыл бұрын

Love u striver ...please make more video of such kind very helpful 😘😘

@RahulKumar-nd2sp Жыл бұрын

Hey! How much dsa topics you have covered?

@PawanSingh-ck2jv Жыл бұрын

this code is giving output as 198 but bool value should only return 0 or 1. also i know that i can get correct output by using & variable as &s. #include using namespace std; bool palindraom(int i,int j,string s){ if(i>j)return 1; if(s[i]!=s[j])return 0; palindraom(i+1,j-1,s); } int main(){ string s="non"; bool k=palindraom(0,2,s); cout