Ep7 - Find all the possible subsets of an array | Power set | Recursion | DSA series
Вставка
- Опубліковано 12 вер 2024
- Let us find all the possible subsets of an array. This is a very important question because it will help us a lot when we will solve future questions. So don't miss out this lecture and watch it till the end.
Practice - bit.ly/39MNFwz
Code available in Cpp, Java, Python - github.com/Lea...
Main channel link - bit.ly/3GBAV7f
DSA Placement series - • DSA Placement series
Recursion playlist - • Recursion
🔴Watch the complete Linked List Series • Linked List Series
To get all updates follow on Instagram
/ frazmohammad
👨💻Utilize free courses, DSA sheet, and articles on Lead Coding website at
Join our telegram channel for all the important announcements
t.me/leadcoding
✨ Hashtags ✨
#DSA #Recursion #Placement #Fraz
Okay I noticed people want vector lecture right ua-cam.com/video/SGyutdso6_c/v-deo.html
Thank you 😊, wanted this one
Yes....❤️ Baki sab thik hai 🔥
yes we want
Hlo everyone , 7.1 Java solution is also not working. Can anyone please add the base condition in that as well..
@@singla__sisters2928 if(i >= v.size()){
ArrayList tP = new ArrayList();
ArrayList tT = new ArrayList();
tT.add(tP);
return tT;
}
check this out,I think this might work.
A small suggestion, while u are solving a question in one Lang many people might not know that language ,so if u divide the screen and show us all language codes it will be much more effective for everyone.like u need not explain all Lang codes just keep them on the divided screen.you can explain just one while we look at that code which we are comfortable. Hope u understand Thankyou:)
Same problem with me too.
Understood, but still its difficult for me to understand through c++ as I prefer java always...
Still managed to understood the concept
7th day ✌️
Consistency ✌️✌️
Bro, can you please share the complete syallabus that you going to cover in these series
@Codewith_AyushLuthra java ka code link kaha hai
@Codewith_AyushLuthra code hai but base condition missing hai? did it work for you?
Hey, is it possible for you to share your java code, it's tough for me understand in cpp
Thank you Fraz bhai for all the hardwork you're doing for us so that we can crack our placements. The content level is awesome. Learning a lot of thing. Was having exams but I'll be regular now to have the most out of this program. One again thank you bhaijaan 💓
In order to get subsets in reverse order just take our last element and pass rest of the array to recursive function.
if(i < 0) return {{}};
helper(v, v.size() - 1);
just do this changes .
Finally I got the solution in easy way..ThankYou! This DSAseries is going to very helpful for students in future also!
WAITING FOR NEXT VIDEO
Much awaited video and now the fun begins as the level of questions increase please bring more and more questions like this Bhaiya
Firstly I am not understand this approach but when you Explain the recursion tree it will be very very easy to understand the whole concept ❤️ enjoying all video with more motivation 🥰
Literally you are just amazing . Intuitive way of teaching
Now i got this one, i have watched many videos got it clear from here only. Thanks sir🙏❣️❣️
Wonderful! , the way you have explained the first approach is just wow.. going great 💥✌️✌️✌️
apne kitna simple bana diya
Call function and do it for short part
Trust recursion
identify base case.
Thank you bhaiya 🌟
At the end of the video, please explain the codes uploaded in python too.
I'm comfortable with that, but sometimes it gets confusing in the steps when understanding on my own.
Maybe the line-by-line explanation would help clarify it too.
I hope you will solve my problem
thank you
Big bro again you have showed ur regularity ❤️❤️. Your lecture series is going to be very interesting day by day because gradually you are increasing difficulty levels which is really helpful and easy to progress. U r uploading these videos regularly so no need to remind you like everyday I did 😂. #justawesome ur lecture...learnt two detailed approach which is even within a perfect time length...keep doing great, I am also doing from my end. Love you
Thanks again bro, each day your comment gives me an energy dose.
Faraz bhai can you please show and explain the JAVA code too of the programs you solve in the video, I'm from a JAVA background and feel difficulty in understanding C++, it would be really helpful if you just walk through the codes of JAVA.
Java code is in description 👍
I have fear of string Data structures but I watched your videos and got it that this is too easy.
Ep 7 is completed. Sorry for the late comment.
Your motivation is amazing. 🌟🌟
I like how you edited the thumbnail with the recursion effect. Creative.
Bro Good explanation especially the first approach is new one which I have not seen before but quite good intuition behind subset finding ❤❤❤❤
Ep7 also done successfully ✅
Bhaiya mza aa ra sbkuchh aap itne achhe se explain krte hai ki koi doubt hi ni rah jata😁
Another thing that we can do is we can sort partial ans in the second for loop, just add sort(x.begin(),x.end()); The time complexity will get a little messed up though but yes, it works here. I tried it out.
#Day_7
Little bit tricky but able to understand
#CONSISTENCY_OP 🔥🔥🔥
Java people will some issue as we move forward if possible explain java code also
@Lead Coding
Hello Sir!! The code for this problem and the order in which the test cases are demanding the ans is , :
vector powfun(vector &v,int i){
if(i
I liked the first approach , Very nice explanation Fraz bhai , Badhiya laga, confidence bhi aa raha hai
very well explained bro. i tried solving this subset problem, i couldn't find a way out, but with the recursion, now i have answer to this type pf problems. thank you
bhaiya would you please include the vector part after the Recursion topic is over ????
It's a request because the vector portion in the code is going over the mind, but I understand the algorithm very well.
Best wishes for upcoming videos
Keep going bhaiya ✌✌
Thankyou bhaiya for sharing your knowledge for free
Starting the lec: here are the key points of this lecture ♥️ All subsets of an array problem:
We could just build up the subset of different size in an array i.e. subset[]. Here are the steps to generate it:
Choose one element from input i.e. subset[len] = S[pos]. We can decide to include it in current subset or not.
Recursively form subset including it i.e. allSubsets(pos+1, len+1, subset)
Recursively form subset excluding it i.e. allSubsets(pos+1, len, subset)
Make sure to generate each set once.
# Function to generate a power set of given set `S`
def findPowerSet(S, s, n):
# if we have considered all elements
if n == 0:
print(s)
return
# consider the n'th element
s.append(S[n - 1])
findPowerSet(S, s, n - 1)
s.pop() # backtrack
# or don't consider the n'th element
findPowerSet(S, s, n - 1)
what is sapce & time complexity of first approach
Question :
Single Program for all subsets of an array or all unique subsets of an array in python
Logic :
for every element in array we have two choices either to consider it or not to consider it
Code:
def primeSet(nums,i,subset,ans):
if i == len(nums):
ans.append(subset[:])
return
#considering ith element
subset.append(nums[i])
primeSet(nums,i+1,subset,ans)
while i+1
Instead of the first way, we can use bit manipulation inside the function to return the answer. a very good video on recursion.
1st approach can be solved by your first submission attempt, just reverse the array in the pwset function, reverse(v.begin(),v.end()):C++
Asalamualikum warhamtullahi wabarkatahu
Jazak'Allah khair bhai
For the amazing video
May Allah reward you in both the world's
Ameen
nice lecture...upto the mark explanation !!
public static void helper(ArrayList arr, int index, ArrayList output) {
if(index == arr.size()) {
ans.add(output);
return;
}
//without ith element
helper(arr, index + 1, new ArrayList(output));
//With ith element
output.add(arr.get(index));
helper(arr, index + 1, new ArrayList(output));
}
Thank you soo much I was too much confused about java solution of this program thanks ☺
Done Understood❤✅
thank u sir im solving problem with u daily and it motivate and helping me lot daily at 6pm im waiting for video and learn daily new things thanks a lot sir
Sir why we have to use vector
This one was quite difficult to grasp, but did it anyway. Needed a lot brain storming, Thanks Fraz
Awesome work
Series going so smoothly and good.thanks @Faraz bhaiya to make this superb series for us
Difficulty level has increased
Bhaiya, in the first approach of solving this problem, we should get the sequencing correct if we just the sort the vector x:partialAns after inserting i'th element i.e v[i]. in second for loop of helper function.
After doing that all test cases were satisfied.
First reach +++
Can you tell sir more briefly this question vector working
Lecture was nice and interesting but for myself 1st approach was difficult to understand, I watched video many times but it is difficult for me to understand but the 2nd one was easy when you explain recursion tree I was able to understand 2nd approach.
Yeh baat😍 ache qs aana start ho gaye
this one is simple with bit
did not understand c++ and this approach
Will be starting this lecture now
In the question it's clearly mentioned that the elements in the subset should be sorted in the ascending order. That's why it gives wrong output
Suru jabardasti kiyen thae....lekin ab maja aa rha h....
Never seen recursion being delivered in such. A easy manner
In second approach you have called the function without the passing the argument(ans vector) as reference.
In previous approach you passed as reference. I also saw a lot videos in which people always pass vector as reference. Can you explain why so??
Sir Can we use like this know sir (vector ans) instead of (vector
A really good contents given by Fraz bhaiya thank you so much bhaiya .
nice lecture bro, it is helpful, Thank u.
Bhaiya I have a suggestion ki either aapne vector padhaya hota or question ko thoda aur detail mei discuss Kiya hota. Because difficulty suddenly increase ho gyi.
Thank you for this course 🙂!!
I Figured Out the first Approach Sequencing Problem!
ask recursion to give power set for starting elements..
Rather asking them to give later elements.
IN OTHER WORDS, GO FROM BACK TO FRONT!
ThankYou !!!✌
vector helper(vector &v, int i) {
if (i < 0) return {{}} ;
// ask helper() to return power set for upto (i-1)th ele
vector partialAns = helper(v, i - 1) ;
// do my own task
vector ans ;
for (vectorx : partialAns) {
ans.push_back(x) ;
}
for (vector x : partialAns) {
x.push_back(v[i]) ;
ans.push_back(x);
}
return ans ;
}
vector pwset(vectorv){
vector ans = helper(v, v.size()-1) ;
return ans ;
}
ha bhaiya approach tho dono bhi right h chaye tho phele i th index ko include krlo phir exclude krdena aur uska vice versa
Ep-7 done
sir i guess the time complexity will be O(n*2^n) because each subset can have n length . please reply
Sir in how many days DSA will be going to complete??
Could you please make a video on how to use vector or everything about vector??
Very good video sir,maja ageya.
aik off topic question, aapnai automate kia hai kya upload karna video ya khud roz 6pm upload karte ho, agar nahi kia hai toh using python u can
I salute your consistency .
Bhaiya ultimately both approaches are same na🤔 just the way of implementation is different because both are using include/not include strategy although I always used second one but amazing explanation bhaiya 🔥
one question, the first one also have O(2^n) TC ?
Very nice video bhaiyya 👍. But won't the time complexity include time taken for pushing a subset to ans array because while pushing it needs to copy into ans array which takes time?
Ep-7 Done
fraz bhaiya there is more efficient approach like swap the element in the vector and then use recursion please add this approach also 🙏🙏you doing great job bhaiya 😌😌
thank you bhaiya for this wonderful lecture
Thanks a lot Fraz sir
i learned a difference b/w mathmatical induction and another method which taught by aditya bhaiya
, method -1 --->so suppose i'm standing at i =0 and my array was 123 , at i =0 i take a decision for i =0 element including it and mera viswass hai apne bade bhai pe ki ab woh 2 and 3 ke liye kaaam karke le aayega when i'm including a ele (mera bhai----> means recursion fun) another decision is not including and after that i'm giving remaining (2 &3 )work to recursion (bhaiya ab tu karke la mere liye, mein thak gya ) , jab mein element nhi include kr raha.
====================================================================================================================================
====================================================================================================================================
code :- void helper (vector nums , vector op , int i , int n , vector &v){
if (i== n+1){
v.push_back(op) ; // base case
return ;
}
// yhaan mein i = 0 pe decision le raha---> including a ele(i=0)
op.push_back(nums[i]);
helper (nums , op , i+1 , n , v); // i= 0 means 1 ka mene including decision le liya aur bol diya bhaiya se 2 and 3 ka including wala ap leke ana mein toh thak gya .
//another decision ---> i'm not including i =0 element which is 1
op.pop_back();
helper (nums , op , i+1 , n , v); // ab again call kr diya bhaiya ko , bhaiya ab mene dusra decision le liya , ab iska kaam b ap karke lao (bichara bhaiya :p).
}
vector subsets(vector &nums ){
// ab yhaan bas zaroorat ki cheeze intialize ki hai jo helper ko chaiye thi krne ke liye
}
------------------------------------------------------------------------------------------===============================================================================
method 2 ->>> adtiya bhaiya wala bas difference ye hai ki method1 mein ek hi jagah pe decision le raha op mein hi yes then fun call(yes wale decision saare ab bhaiay leke aayege ) and no decision then fun call (no wale saare bhaiya leke aayege), method2 mein op1 and op2 leta hoon phele previous op ko dono mein copy krta hoon and i'm always take a decision in op1 so mein op1.push_back(nums[i]) and op2 mein humesa no wala decision le rha toh usme kuch b push nh kr raha , and then fun call kr duga ek fn m op1 pass krunga and ek mein op2 . that's it .
dono similar hi hai bas smjne ka intution alag alag hai . ha pata hai meri english shi nhi hai lekin hope hai bhaiay ke sath improve ho jyngi .
ep7done,,, love u bro🥰 best off luck
Thank you sir....day 7 check....
very well explained
very nice explanation
lecture 7 is understood and done.
Today I am revising this lecture before watching toddya's 10th lecture. Bhaiya what will be the recusrion tree for 1st approach?
I was very excited about the course ... But I don't know c++ .. up till now I could understand by seeing the Java code.. but now I cannot understand... Please do something fraz bhaiya... Explain the Java solution too😞😞
i learned one more thing helper fn mein return type non void ke ky disa hai aur void lene se ky faayde hoge ----> agli baar jab b aao toh khud phir se sochna .(ye khud se hi socha ).
Although my exams are going on, still seeing your videos to get a clear my DSA concepts. Thank you sir for this wonderful series!
Keep going bro 🔥.
You gonna make it
@@LearnYardYT Thank you so much sir for this motivating comments!! Means a lot☺️
@@LearnYardYT The difficulty level was little more as compared to other lectures, but concept got cleared!! Thank you sir for such wonderful lectures
Ur lectures are amazing fraz!! So much to learn! 😊🤗
- Rahul
Fraz bhaiya this recursion series is insane 💯
Lecture - 7 Completed ☑
#Dsabyfaraz ❤
#recursion💯💯
nice explanation keep up the good work.
Wonderful Bhai🥰
1st approach ka time & space complexity O(n) hoga???
Please reply
Thanks sir for such a nice content ❤️❤️
Very nice explained sir.
love from Nepal.
Java code unable to understand which is in github try to make it clear it will give errors
sir, i have a doubt in method1 :
//fix| why arent we taking 'ans' as input in the helper func? 'ans' to update ho rha hai, to kya fark nahi parega?
//fix| doubt explained :
// my doubt:
/*
helper (i=0)
{
pA = helper (i=1)-------- in this, pA = helper (i=2) is called and then we declare 'ans' [1]
now, we declare 'ans'[2] in this scope.
//fix | how is 'ans'[1] == 'ans'[2] ?
}
*/
i got the answer. the ans[1] and ans[2] are actually different. ans2 returns the edited value to partialAns in scope x. and in that scope x. we create a new 'ans' variable which is returned to further partialAns. since ans1 and ans2 are functioning independently, theres no need to pass 'ans' to 'helper function'
Day 7, here we go 🔥🔥
bhaiya aj meiin smaj gya mathmatical induction wala funda thoda thoda sa , ab bas practice krni iss intution ki bas
Present ! Sir Would Highly request to you Please tell us the upcoming video topic ! So we just easily cover that topic ! ✔🙌
Waited one ❤️
Day 7 Done waiting for next lecture 😀😀😀😍😘
Very helpful fraz bhai
Day 7 completed✨
Waiting for next lecture ☺️
bro java code is not clear for first half can u write code in detail in future
very helpful