L6. Recursion on Subsequences | Printing Subsequences

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.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------------------------------- 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.o...
Checkout Striver's Handles: linktr.ee/take...

[@jaimitkumarpanchal7603]

Man i usually don't comment on KZbin 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)

[@stain5570]

hii, may I know what are you doing right now

[@samratpatel8060]

@@stain5570 he is a SDE-3 at CornHub

[@dgvj]

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

[@AbhinavKumar-tg4il]

after watching 3 times, now understood. Those who are not able to understand, it's okay, retry, you will get it, and after that you will feel good.

[@ShubhamSinghMr.s]

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]

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

[@VollalaPavanSathwik]

@@pehdntene6473 import java.util.ArrayList; import java.util.List; public class rec_subseq { public static void main(String[] args) { int[] arr={3,1,2}; ArrayList list = new ArrayList(); ArrayList li= new ArrayList(); subseq(0,arr,list,li); System.out.println(li); //System.out.println(li.toString()); } static ArrayList subseq(int i,int[] arr, ArrayList list,ArrayList li) { if(i>=arr.length) { li.add(list); return li; } list.add(arr[i]); subseq(i+1,arr,new ArrayList(list),li); list.remove(list.size()-1); subseq(i+1,arr,new ArrayList(list),li); return li; } } Try this

[@phaneendra_guduru]

Thank you brother 😊

[@tharundharmaraj9045]

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

[@potatocoder5090]

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

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

thanku so much brother

[@sureshgarine]

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

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

[@adityadeshbhartar7172]

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

[@jyotirmoydey7558]

This guy makes recursion look easy and fun. Kudos to you! Amazing job, very inspiring!

[@habeeblaimusa4466]

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

[@yotowilliam5465]

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

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

[@NitishKumar-yy9kn]

if we pass the vector by value, removal will not be needed

[@jitendrakumar-vv8ho]

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.

[@pranaycc]

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

[@jitendrakumar-vv8ho]

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

[@Jonathan-be7gj]

​@@pranayccthat is not the problem, problem is why We r stacking 3 over 2 and 1...also how first person came with this solution

[@ardhidattatreyavarma5337]

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

[@SumitTiwari-f7t]

Thankyou for making videos of recursion and covering all topics. It gives me confidence and boost-up in my rating.

[@ashwanisharma8903]

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]

He is unique XD

[@sanjayhazra181]

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

[@abishekbaiju1705]

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

[@AngadSingh97]

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

[@soumyajeetsengupta3064]

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

[@soorma7869]

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

[@studynewthings1727]

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

[@RishabhJain-iz5xk]

HANDS DOWN BEST EXPLANATION ON INTERNET!

[@samsmith3961]

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

[@madhujustin2124]

STARTED YESTERDAY, IT CAN BE HELPFUL FOR THOSE WHO STARTED NOW...LIKE ME... PYTHON CODE FOR THE SAME IS: def subseq(index, current,arr): if index >= len(arr): print(current) return current.append(arr[index]) subseq(index+1, current,arr) current.pop() subseq(index+1, current,arr) arr = [3,1,2] index=0 subseq(index, [ ] ,arr)

[@SuperWhatusername]

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

[@azaanakhtar1974]

Uh are write in which language Cpp Or java

[@azaanakhtar1974]

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

[@SuperWhatusername]

@@azaanakhtar1974 CPP

[@ratanmasanta3210]

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

@@ratanmasanta3210 thanks buddy

[@arnabkundu1648]

I have understood it extremely well. Thank you sir.

[@sagarsinha6561]

Hey Striver, your approach is superb. However, I have followed another strategy which is more intuitive for me, the code for which is: def fn(i, n, arr, osf): if (i >= n): print(osf) return fn(i+1, n, arr, osf) fn(i+1, n, arr, osf+str(arr[i]))

[@sagarsinha6561]

In your way, it can be termed as don't pick-pick strategy (yours being pick/remove) 😅

[@smoothierudiee]

thank u so much striver ! i was struggling with this one and i finally understood this using recursion tree.. THANK YOUUUUUUU

[@vvssreddy903]

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

[@arshadshaik4961]

When we reach I=3 we actually increase for the branch which is going through right side for left side branch also we get I=3 only because we had called the both right side and left side branches in same function which is f(2, {3, 1}). Just go with tree and you can easily understand

[@rneditz3250]

Is Subsets and Subsequence means same thing???

[@saurabhtamta7295]

Susbets don't have to maintain order of the original sequence while subsequence do

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

[@mr.rexalan5576]

I can understand the code, but i can't able to think recursively on my own to code. Is there any solution for this

[@santhoshswamyv5627]

try to draw the recursive tree like him to get flow with the recursion

[@brp3522]

Try and fail then google is the only way I was in your position but today I conquered the recursion wholly. All the best bud

[@tarun1684]

Apart lecture..vdo end m jo gaane ki tune chlti h.. like it..😂😂❤

[@udaykulkarni5639]

Man! This is crazzyyyy!! I never really comment on KZbin. 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😊❤

[@Cool96267]

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

[@preetiipriya]

found?

[@Dheeraj-ed6rr]

@@preetiipriya Leetcode 78

[@akshanshsharma6025]

@@Dheeraj-ed6rr thanku bro

[@Codebond7]

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

[@vinnuhary2198]

mad respect to this man for keeping it super simple

[@sharmakartikeya]

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

[@akshaybhagwat6179]

The best explanation ever exist on the youtube.

[@iitimunda]

02:18 Generate all subsequences for an array using recursion 04:36 Understanding the structure and pattern of code is crucial for solving problems. 06:50 Code implementation to create a subsequence using recursion. 09:16 By making recursive calls with different indices and choosing whether to include the last element, you can generate all possible subsequences of an array. 11:27 Remove elements from an array based on specific conditions. 13:39 Understanding the concept of adding and removing items in a sequence 15:42 Printing the values in a recursion tree 17:46 Printing subsequences using recursion 19:38 Print a data structure to display the subsequence 21:20 The algorithm involves picking or not picking elements from a given array. 23:10 Time complexity is 2^n and space complexity is O(n)

[@ashokdurunde1814]

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

[@omkarwarule5483]

one of the beautiful play list for recursion on you tube

[@sumitvishwkarma6907]

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

[@sadmanmehedisivan6581]

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

[@torishi82]

Bhai tum mahan ho. Samaj aa gaya.

[@gwalaniarun]

Awesome man, love your explainatiton.

[@arohikarhade1954]

First of all, AMAZING and very helpful video. Thank you for all your effort. P.S. am I the only one who notices that he uses 'a couple of options' to tell us we have specifically 2 options. Not hating at all but I just got so confused at first haha.

[@sojwalgosavi4406]

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

[@chandan1929]

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

[@takeUforward]

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

[@AmarjeetKumar-to9ub]

// Is it correct ? string s="Hello"; void solve(string t,int i){ if(i==s.size()) { cout

[@bazeer1498]

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

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

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

[@veekshithcb]

You have to keep it in your head everyday till your . retirement......

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

[@anshvashisht8519]

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

[@joeyaintwaffling]

Aur tarakki mile aapko bhai, kya samjhate ho

[@parthsalat]

Thanks a lot for this priceless video!

[@AkshatMehra-l4b]

Amazing, lost for words 👏🏽👏🏽👏🏽

[@laginenisailendra1959]

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

[@sreenandini766]

Super explanation sir .Thank you so much❤️

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

[@sumanthvarmakarampudi7251]

Super Clear, Great Effort Always thankful to you sir

[@sriramrajkumar2774]

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]

i have same doubt couldnt understand that

[@nahidfaraji5069]

No one can beat this Explanation.

[@factsmotivation7728]

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

[@user-mv6wh5rp6w]

Java code to find for Subsequences of given string... public static void main(String[] args) { String str = "abcd"; ArrayList results = new ArrayList(); gss(str, 0, new StringBuilder(), results); System.out.println("Number of subsequnces:" + results.size()); System.out.println("subsequnces:" + results); } private static void gss(String str, int idx, StringBuilder subSeq, List results) { if (idx >= str.length()) { results.add(subSeq.toString()); return; } subSeq.append(str.charAt(idx)); gss(str, idx + 1, subSeq, results); subSeq.deleteCharAt(subSeq.length() - 1); gss(str, idx + 1, subSeq, results); }

[@aashapun6533]

Thank you so much. Worthy Content!!

[@_sf_editz1870]

java code : if (index >= n) { System.out.println(list); return; } // Include the current element in the subset list.add(arr[index]); printSub(arr, list, n, index + 1); // Exclude the current element from the subset list.remove(list.size() - 1); // Remove the last element (backtrack) printSub(arr, list, n, index + 1); }

[@brp3522]

JAVA CODE : import java.util.ArrayList; import java.util.Scanner; public class demo { public static void func(ArrayList arrlst, ArrayList res, int index) { if(index >= arrlst.size()) { System.out.println(res); return; } func(arrlst, res, index + 1); res.add(arrlst.get(index)); func(arrlst, res, index + 1); res.remove(res.size() - 1); } public static void main(String[] args) { Scanner obj = new Scanner(System.in); ArrayList arrlst = new ArrayList(); arrlst.add(3); arrlst.add(1); arrlst.add(2); int indx = 0; func(arrlst, new ArrayList(), 0); } }

[@Highlights_Point]

Great Explanation sir i feel the recursion today

[@harshilsutariya1793]

striver content 💥 >>>

[@saketmehta6697]

For Java lovers: In Java, ArrayList does not have pop feature so you can use a Stack Hope this'll help someone! import java.util.Stack; public class Striver { //functional way public static void main(String[] args) { int[] inpArr= {5,7,8}; Stack res=new Stack(); print(inpArr,0,res); } private static void print(int[] inpArr, int i, Stack res) { if(i==inpArr.length) { res.forEach(s->System.out.print(s+" ")); if(res.isEmpty()) { System.out.println("{}"); } System.out.println(""); return; } //do res.add(inpArr[i]); //recur add a element print(inpArr, i+1, res); //undo res.pop(); //not add print(inpArr, i+1, res); } }

[@sushantkharat4856]

You can use arr.remove(arr.size()-1); to remove from arraylist.

[@saahilsharma6537]

Java Code :- public static void func(int i,List a,List arr) { if(i>=arr.size()) { System.out.println(a); return; } a.add(arr.get(i)); func(i+1,a,arr); a.remove(arr.get(i)); func(i+1,a,arr); } }

[@saira18926]

thank you

[@k10n28]

i was looking for the same thanks

[@hrithikrudra4292]

Bro,thnaks for this..But I am facing some problem while taking the input as array.. Error:For 2 it is showing out of bound index..Anyone help me out in this,issue??Thanks in advance My code: /** * PrintAllSubsequence */ import java.util.*; public class PrintAllSubsequence { static void printSubsequence(int index,ArrayList res,int arr[]){ if(index==arr.length) { System.out.println(res); return; } //taking the arr input res.add(arr[index]); printSubsequence(index+1, res, arr); //not taking the array input res.remove(arr[index]); printSubsequence(index+1, res, arr); } public static void main(String[] args) { int []arr={3,1,2}; ArrayList res=new ArrayList(); printSubsequence(0, res , arr); } }

[@swapnilnandedkar3930]

@@hrithikrudra4292 change your res.remove(arr[index]); statement with res.remove(new Integer(arr[index])); arrayList have 2 remove method one with index and other with object. res.remove(arr[index]); this statement try to call remove with index because arr[index] giving int and Collection only work with objects. Because of this you are getting outofbound. Either use new Integer(arr[index]) or convert int []arr={3,1,2} to arraylist

[@hrithikrudra4292]

@@swapnilnandedkar3930 thanks,bro..👌👌

[@ritvi5717]

amazing teacher thank you so much :)

[@puranjanprithu6337]

the tree simplified everything...thanks man

[@alifaisal1475]

YOU ARE AWESOME! Explained this difficult topic with ease, and in-depth as well. ❤‍🔥

[@niitteenpathak5620]

Thank you so much for amazing explanation.

[@sagaravhad5198]

very good example try on room. thanks.

[@ElonMusk-ez5xz]

So this comes under parameterized recursion correct?

[@anandkishor5737]

# Printing all Subsequences. def subseq(ind,res,arr,n): if ind >= n: print(res) return res.append(arr[ind]) subseq(ind+1,res,arr,n) # Take CASE. res.remove(arr[ind]) subseq(ind+1,res,arr,n) # Not-Take CASE.

[@TheMa11nu]

We could have gone with non take case first, so that we don't remove from the list.

[@Yash-uk8ib]

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]

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

[@shauryatuli2241]

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]

@@shauryatuli2241 ok

[@manishchandrapaneru.o5]

The most beautiful explanation ✅

[@shivalikagupta3433]

Thank you!!! Extremely wonderful!!!

[@takeUforward]

You're very welcome!

[@SaketAnandPage]

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

[@thisisrajneel]

why does the vector have to be passed by reference? at 20:07

[@purushottamkumar3140]

Hats'Off to this Guy. Amazing

[@chanish163]

Why can't we first not take and then take which saves our .remove() complexity?

[@adityajain1205]

yes we can do this

[@miragranger4685]

No, we cannot skip the .remove() even if we first do "not take" and then do "take" because if the element is not removed after the take, it will remain in the ds vector and will affect the combinations that come after that. Striver has explained it at 22:22 .

[@chanish163]

@@miragranger4685 got it, thanks a lot

[@the.arty.heart_]

@@miragranger4685 We can actually skip .remove() , by receiving ds vector without reference

[@arnabkr7302]

The Java Code : public static void subseq(int ind, ArrayList arr, int[] num,int n){ if (ind >= n){ System.out.println(arr.toString()); return; } // Pick Condition arr.add(num[ind]); subseq(ind+1, arr, num,n); // ThIS is the MAin Change arr.remove(arr.size() - 1); // Not Pick subseq(ind+1, arr, num,n); }

[@shalinikumari6626]

Hii, striver .I am your big fan, one day i will crack google and meet you there. I observe something about you is your fav colour is red and i thnik you like unknown brain electronic music♥

[@keertilata20]

loved it, thank you so much :)

[@kanishkasingh2324]

Humour and wit with abundance of knowledge and talent!

[@devanshukumar931]

Nice Explanation.

[@anishmishra4988]

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.

[@md.sahidulislam3152]

You are the best....Love from Bangladesh

[@yashasvasharma4689]

Why did we pass vector as a reference in the implementation?

[@dpxy1599]

it is working like a magic tuff to believe will have to pend much time in this.