L6. Recursion on Subsequences | Printing Subsequences
Vložit
- čas přidán 24. 12. 2021
- 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
Man i usually don't comment on CZcams 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.
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)
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.
Huh
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
He is unique XD
Yup, also some just mug up from chatgpt and code .
Finally, the day has come to understand and as well code for the same.
💯💯
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);
}
It helped me a lot bro
Very helpful
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
Best series on recursion in the internet. Thanks alot for your time and effort.
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);
}
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);
}
thanku so much brother
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
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 :)
Amazed by your lessons, i feel like i know recursion better than before, thanks bro.
this has been beautifully explained ..I've been searching for this explanation for hours now and this was good
Man! This is crazzyyyy!! I never really comment on CZcams. 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😊❤
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...
indeed, it's a wonderful explanation. thanks for taking time and doing this for community
Simple english....No confusions......... Great work
Thankyou STRIVER, for explaining the subsequence problem in a awesome manner.
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!
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 !!!!!!
it was quite difficult to understand
no problem.
[] and arr[] are different and need to be passed through the recursion.In the explanation it might have confused.
after this video I solved subset sum pretty easily. Thank for your crystal clear explanation
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++.
How to learn recursion?
You are taking great efforts and we are learning from you Striver.
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.
if you want to remember it like using " take " and "not take " you should follow that
I watched it once didn't understand, but after that watched again by following him with a pen and paper and understood completely.
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.
Bro how u understand recursion?
Thank you so much! You're an amazing teacher :)
That really was one of the best way to explain sub-sequence.
HANDS DOWN BEST EXPLANATION ON INTERNET!
I had to watch this video for more than 5 times.
God bless you bro
It will be so cool if you can add the codes in the description!
Understood. will complete recursion today no matter how much time it takes.
Finally it's crystal clear... After watching this video 3-4 times
Earlier I was learning recursion and dynamic programming together and that was my mistake. Thanks for creating this playlist and awesome explanation.
Uh are write in which language Cpp Or java
I wrote in java bt i faced an error working with array and list
@@azaanakhtar1974 CPP
@@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);
}
@@ratanmasanta3210 thanks buddy
Super Clear, Great Effort
Always thankful to you sir
Hey Striver, Could you also please attach the link of the respective leetcode questions?
found?
@@preetiipriya Leetcode 78
@@Dheeraj-ed6rr thanku bro
one of the beautiful play list for recursion on you tube
thank you so much for the recursive tree it helped a lot
if I don't pass the vector &ds as reference then I don't have the need to ds.pop_back() correct ??
Then it creates a new copy everytime, which will lead to tle :(
Thanks you so much sir for this wonderful content ,i loved with recursion sir 🙏🙏
Awesome man, love your explainatiton.
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
May God bless you with all the health and wealth you need. I understood it.
Thank you so much. Worthy Content!!
Explanation was good but have one question though why we need to create res.add(new ArrayList(ans)); everytime new arralist?
Now I understand this subsequence, after watching famous courses of CN, CB, I don't understand from them that deeply
Super explanation sir .Thank you so much❤️
I have understood it extremely well. Thank you sir.
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[]) ????
yes because when you do i+1 it will only increment inside that called function but outsite the function it is still 2
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.
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?
i have same doubt couldnt understand that
If we want to add subsequence inside another array what to do?
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.
Just don't stop uploading anytime you feel you are not getting enough views.
Good Luck.
Great Explanation sir i feel the recursion today
Thank you!!! Extremely wonderful!!!
You're very welcome!
the tree simplified everything...thanks man
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.
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
mad respect to this man for keeping it super simple
The best explanation ever exist on the youtube.
amazing teacher thank you so much :)
Thanks a lot for this priceless video!
So this comes under parameterized recursion correct?
watched it 4 times to understand this above 80% ,nice
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 ?
No one can beat this Explanation.
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 .
loved it, thank you so much :)
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.
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.
What's difference between this and subset video in ur Playlist can you please explain
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
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
in the final code we don't need to pop_back from the vector
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??
after watching 5 times with paralally coding ..now i finally understand the whole concept of take and not take lol😆
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 .
Really good explanation
!
It's just amazing what an explanation.
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)
all recursive solutions can be done using iteration but the vice versa is not true.
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 .
@@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?
@@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 .
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!!
Ha shi h tu bhi i==n hi shi h
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
@@shauryatuli2241 ok
YOU ARE AWESOME! Explained this difficult topic with ease, and in-depth as well. ❤🔥
Hats'Off to this Guy. Amazing
first time I understand this. Thanks bro
Understood!! Awesome explanation!!
at 11:48 why it removed arr[2] and not arr[3] because the last index was 3 ?
// Is it correct ?
string s="Hello";
void solve(string t,int i){
if(i==s.size()) { cout
at 8:05 i cant understand if an empty array is passed then hown can we say that the size inside the function will be 3?? can anyone tell me this?
Love the way you explained 💯💥
Thank you so much for amazing explanation.
Man this was an amazing way of explaining!!!!!!!!!!!!!!!!! l
Why did we pass vector as a reference in the implementation?
Amazing explanation, can we reduce time complxity
hey please provide us the solution of this question given in your DSE sheet using recursion on GFG
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
Beautifully explained
Awesome explanation, understood!
One doubt is that why we are passing vector as reference whereas passing array as parameter?
Array are are passed as reference in cpp whereas vectors are not, and we need the modified vector in each recursion call. :)
why does the vector have to be passed by reference? at 20:07
Can someone please explain why at 15:42, when we move to 'not pick' any value from array we still increase our index value to 1?
Coz if u don’t pick, why will u stay on same index.
@@takeUforward Thank you sir for replying. I got it now. 👍
We could have gone with non take case first, so that we don't remove from the list.
So useful video. Thanks 👍🙏
Not getting the space complexity. Please explain in further details if possible. Thanks!