L6. Recursion on Subsequences | Printing Subsequences
ฝัง
- เผยแพร่เมื่อ 26 ก.ย. 2024
- 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...
Man i usually don't comment on TH-cam 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)
hii, may I know what are you doing right now
@@stain5570 he is a SDE-3 at CornHub
Best series on recursion in the internet. Thanks alot for your time and effort.
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.
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
@@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
Thank you brother 😊
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 :)
Simple english....No confusions......... Great work
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
indeed, it's a wonderful explanation. thanks for taking time and doing this for community
Amazed by your lessons, i feel like i know recursion better than before, thanks bro.
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...
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
This guy makes recursion look easy and fun. Kudos to you! Amazing job, very inspiring!
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
if we pass the vector by value, removal will not be needed
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 .
after this video I solved subset sum pretty easily. Thank for your crystal clear explanation
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 !!!!!!
I had to watch this video for more than 5 times.
God bless you bro
Thankyou STRIVER, for explaining the subsequence problem in a awesome manner.
Thankyou for making videos of recursion and covering all topics. It gives me confidence and boost-up in my rating.
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
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
I can understand the code, but i can't able to think recursively on my own to code. Is there any solution for this
try to draw the recursive tree like him to get flow with the recursion
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
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.
Do the dry run buddy, recursion is all about stack tracing and tree tracing 9:50
@@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 ???
@@pranayccthat is not the problem, problem is why We r stacking 3 over 2 and 1...also how first person came with this solution
this has been beautifully explained ..I've been searching for this explanation for hours now and this was good
I watched it once didn't understand, but after that watched again by following him with a pen and paper and understood completely.
Is Subsets and Subsequence means same thing???
Susbets don't have to maintain order of the original sequence while subsequence do
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
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?
Excellent explanation, itni baar dekhne ke baad it is even possible to watch at 3x and revise easily, which is amazing.
Man! This is crazzyyyy!! I never really comment on TH-cam. 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😊❤
HANDS DOWN BEST EXPLANATION ON INTERNET!
Hey Striver, Could you also please attach the link of the respective leetcode questions?
found?
@@preetiipriya Leetcode 78
@@Dheeraj-ed6rr thanku bro
Finally it's crystal clear... After watching this video 3-4 times
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 :(
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)
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)
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]))
In your way, it can be termed as don't pick-pick strategy (yours being pick/remove) 😅
Understood. will complete recursion today no matter how much time it takes.
It will be so cool if you can add the codes in the description!
Thank you so much! You're an amazing teacher :)
Just don't stop uploading anytime you feel you are not getting enough views.
Good Luck.
Apart lecture..vdo end m jo gaane ki tune chlti h.. like it..😂😂❤
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
I have understood it extremely well. Thank you sir.
thank u so much striver ! i was struggling with this one and i finally understood this using recursion tree.. THANK YOUUUUUUU
one of the beautiful play list for recursion on you tube
Awesome man, love your explainatiton.
That really was one of the best way to explain sub-sequence.
Now I understand this subsequence, after watching famous courses of CN, CB, I don't understand from them that deeply
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
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.
thank you so much for the recursive tree it helped a lot
The best explanation ever exist on the youtube.
Bhai tum mahan ho. Samaj aa gaya.
Why can't we first not take and then take which saves our .remove() complexity?
yes we can do this
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 .
@@miragranger4685 got it, thanks a lot
@@miragranger4685 We can actually skip .remove() , by receiving ds vector without reference
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.
You are taking great efforts and we are learning from you Striver.
Super explanation sir .Thank you so much❤️
Explanation was good but have one question though why we need to create res.add(new ArrayList(ans)); everytime new arralist?
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);
}
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.
Thanks a lot for this priceless video!
mad respect to this man for keeping it super simple
why does the vector have to be passed by reference? at 20:07
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
after watching 5 times with paralally coding ..now i finally understand the whole concept of take and not take lol😆
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 .
Thank you so much. Worthy Content!!
Can we call just before addition and after addition? Why are we removing it?
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);
}
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);
}
}
thank you
i was looking for the same
thanks
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);
}
}
@@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
@@swapnilnandedkar3930 thanks,bro..👌👌
Thanks you so much sir for this wonderful content ,i loved with recursion sir 🙏🙏
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
You have to keep it in your head everyday till your . retirement......
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.
I have one doubt for eg:f(2,[3])=>take f(3,[3,2])=>not take [3,2].remove(a[2]) here is my doubt the array as two elements[3,2] then how we remove a[2] ?? array has ony two elements[3,2] then the index are 0,1.
Exactly same doubt !!!
@@consolecoder6724 In their explanation video they taught us to remove(a[i]) in code simply use pop()method to remove the last element in an array. It works well👍
@@sudharshan3863 instead of using list.remove(index) use list.remove(list.size()-1)
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
// Is it correct ?
string s="Hello";
void solve(string t,int i){
if(i==s.size()) { cout
So this comes under parameterized recursion correct?
May God bless you with all the health and wealth you need. I understood it.
amazing teacher thank you so much :)
Super Clear, Great Effort
Always thankful to you sir
Great Explanation sir i feel the recursion today
can you please explain how space complexity is O(n) ?
slight iteration error in the recursion tree , f(3,[1,3]) will directly return to f(1,[3]) and cant evaluate if f(2,[3,1]) is done or not
bhai adityA verma se krlu ?
Aur tarakki mile aapko bhai, kya samjhate ho
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 .
Why did we pass vector as a reference in the implementation?
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 .
Amazing, lost for words 👏🏽👏🏽👏🏽
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
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);
}
}
You can use arr.remove(arr.size()-1); to remove from arraylist.
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 ?
Not getting the space complexity. Please explain in further details if possible. Thanks!
No one can beat this Explanation.
loved it, thank you so much :)
Dint understand why time complexity is 2^n * n and not just 2^ n. Any help anyone?
striver content 💥 >>>
Lol learning DSA is like anime training, once in a while we get powerups like these.
Can you pls discuss the code for printing the subsets in lexicographical order? Interviewbit asks for ordered printing whereas other sites don't.
I think if you sort the array before this algo, you will get lexicographical.
@@gauravkr74 No it doesn't work like that, do check out interviewbit if you want to understand my question.
Store it some vector instead of printing, and at the end sort and return it
@@takeUforward I did that to solve the question after watching your code beyond stream but there was a solution in the editorials which didn't require sort. I know TC wise it doesn't make any difference but time wise it does, so just want to understand the logic behind it.
@@vaibhav_singhal It might have used Priority Queue (not STL) to store the data then it doesn't require to sort the data.
Thank you so much for amazing explanation.