Ep10- Subset II problem | Find all UNIQUE subsets of an array with duplicate elements | Recursion
ฝัง
- เผยแพร่เมื่อ 11 ก.ย. 2024
- In the lecture number 7 of the recursion series, we saw how to find all the subsets of an array, but in this lecture we will see, how to find all UNIQUE subsets of an array with duplicate elements. Make sure that you watch lecture no.7 before watching this video.
Practice - www.codingninj...
Code available in Cpp, Java, Python - github.com/Lea...
Pre-requisites:-
1. Ep7 - Find all the Subsets of an array
• Ep7 - Find all the pos...
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
Summary of the lecture:
1. In Subsets-I, we have all the elements as unique. That's why our Pick and Don't Pick conditions were working fine.
2. In Subsets-II, we will have duplicate elements. But we want our final ans to contain only unique subsets.
3. We can achieve it by counting only one occurrence of an element and skipping all its rest occurrences in arr[]
4. We need to first sort the given vector arr[]
5. For don't pick condition, we will first check whether arr[i]==arr[i+1] or not. If so, we will ignore the rest occurrences of that particular element.
5. Time and Space Complexity will remain same[in worst case we will have unique elements only]
Good job🚀
@@LearnYardYT Thank you sir
@@avaneshwari666 Sets will definitely work ma'am but the main issue is that it will consume a lot of time everytime we use find() function , so a better approach is to just skip all the duplicate elements. In this way both our time and space complexity is increased
@@avaneshwari666 Mam set can also work and the time complexity will remain O(2^n) using the pick and non pick algo for the subset with some minor changes. This is the code below with some minor changes :-
#include
void subsets(int i,int n,vector &arr,vector &subset,vector &ans_set)
{
//Base case
if(i==n)
{
ans_set.push_back(subset);
}
else
{
subset.push_back(arr[i]);
subsets(i+1,n,arr,subset,ans_set);
subset.pop_back();
subsets(i+1,n,arr,subset,ans_set);
}
}
vector uniqueSubsets(int n, vector &arr)
{
// Write your code here.
sort(arr.begin(),arr.end());
vector subset;
vector ans_set;
subsets(0,n,arr,subset,ans_set);
set ans_dup;
for(auto i:ans_set)
{
ans_dup.insert(i);
}
ans_set.clear();
for(auto i:ans_dup)
{
ans_set.push_back(i);
}
return ans_set;
}
@@avaneshwari666 Welcome mam
When someone says how to master recursion then i send them the link of your channel. The best playlist of recursion on youtube.........thank you fraz bhaiya for providing these quality lectures.......lots of thank you ..My IDEAL..🙏🙏🙏🙏
and then you will have people like me who will surpass your leetcode profile using links and will flaunt it to you only in particular.. doesn't it itches your balls..
Hey, Thanks for this playlist. I always had issues in understanding recursion problems. The main thing I liked about your playlist is that you have added prerequisites for all the videos. If I'm not able to understand something I know what I'm lacking currently and can refer the videos in the prerequisites. This made even the concepts I never understood over months of leetcoding now. Thanks a lot !
Day 10 🔥.
only 30% of the people are able to be consistent for 10 days or more and if u are one of them , give urself a pat on the back , and good luck for the rest of the course , hopefully we will be together for this entire journey 💯
I have always feared recursion but your way of teaching has made it so easy. Thank you so much for this extremely well explained video.
I did not understand this from other's solutions. But this approach made me understand, its much easier and intuitive
day by day, lectures are getting more interesting. Good video. Waiting for tomorrow.
just learned a new way to approach this problem.. best one till now
Bhaiya thank you so much........I can say this is the best playlist of recursion so far !!!!!
In the beginning, I was not able to understand, I have also commented on the 7th video that it's difficult to understand, but today even before the video started I was able to code a recursive on my own, That's because of you bhiaya.
Thank you so much bhaiya.
14:54
Worst Case Time Complexity: O(2^N)
Space Complexity:
O(N)
This is mainly because in the Worst Case we will have all unique elements and the maximum number of nodes will be 2^N , calculated by sum of GP series( explained in lecture 7)
we can use a map to store the vector we have created till now by picking or not picking and can ignore repeated ones as they will be same so map will consider them one
@@srajansohani464 Yes we definitely can but that will increase our Time Complexity and might give us TLE. So we prefer to use it this way using While Loop
@@srajansohani464 I had the same intuition. In fact , I have even implemented it this way and commented it here somewhere. Hope you find it 😂
If we are using a set in these type of questions then the time complexity will not reduce so these type of optimizations helps us to understand code better thanks for selecting best questions in sequence every day❤❤❤❤❤❤❤❤❤
Set wont work here. It will give error. I will explain with an example here.
For eg take an array=[5,5,3,5].
If you run the program using set it will produce an output =
3
3 5
5
5 3
5 3 5
5 5
5 5 3
5 5 3 5
5 5 5
If you run the program using vector it will produce the output =
5 5 3 5
5 5 3
5 5 5
5 5
5 3 5
5 3
5 5
5
5 3 5
5 3
5 5
5
3 5
3
5
Now if you observe them carefully set considers those two subsets equal or duplicate if they have same element in the same index or position.
But according to the question they are taking those subsets as equal who have same elements irrespective of their position or indexes.
i.e according to the question [3,5] and [5,3] are also equal. But set doesnt remove them.
Therefore the original output for array=[5,5,3,5] is =
3
3 5
3 5 5
3 5 5 5
5
5 5
5 5 5
watched so many videos on this , but you explained really well brother without making it complex
video is of 16 min but time needed to get it 1-1.5 hours 😅
Revise previous notes + watch video + Notes + Question practice on code Studio.
Best part is that we are consistent !!!🤩
Consistency is the main key here. Many people start, but they leave it when the concepts start getting harder and harder. So stay consistent. This one hour which you have spent now, will play an important role in your journey of mastering recursion.
@@LearnYardYT haa bhaiya bahot maza aa rha hai😁😁
Actually this is my first series of any dsa concept on TH-cam 🙏🙏
Itna maza aa rha ki aapka linked list wala series bhi kar rhe
This is very helpful lecture, I watched n number of videos but this make me understand where we are making the duplicate subsets
Complete Day 10 ❤️
Similarly working on your oops concepts. Bhaiyya you provided oops sheets enough for placement?... enjoying all you videos with regular consistent ❤️
#lecture 10 completed 😊consistency
thanks, you really helped !!
Aaj 6 se phle hi....you are making us more consistent!😎💯 Awesome content smjh aa rha hai ache se, ThankYou Fraz Bhaiya🙋♀️🤟thankyou so much.
WAITING FOR NEXT VIDEO
Lecture 10 Done 💝💝👍👍👌👌👌🙌 waiting for the next Lecture 🤞🤞
At last, I've found what I was looking for. Thank you so much.
Thankyou bhaiya for helping us learn this for free
Previously:
DSA...DSA...DSA I don't like it, I avoid.
Now(after watching your lecture):
But DSA likes me. I can't avoid 😂
can you please explain me why are we skipping duplicate values only in the case of ignoring the element
@@gauravshukla5203 we have to find the unique combinations....so think how duplicates are formed..it's by having duplicate elements...so if we ignore duplicate elements..our job is done
Yes, I submited this question before 1 day. But thank you for this video.
thanks sir I was really messed with this question you helped me!
Thank you very much Fraz for your efforts to provide quality content. I became fan of your explanation. Keep up good work.
Good Explanation
Can you please explain this problem in Java code
Because logic mentioned in the Java code is completely different
It would be difficult for you to make seperate video so can you please solve this in Java in doubt solving session
This would be helpful 🙏🙏
used map to store every subset and not repeated it by checking previous occurrence but your approach is good
Sir I appreciate the hardwork you are putting for us and providing such beautiful explanations. But isnt 3 months time very less for this course. If we do 1 question one day then 90 questions will be done in 3 months. Are 90 questions enough for cracking placements?
One thing we will have to understand, any course would not make you solve 500 questions.
You have to to solve it, learn from here apply in contests.
We are also organising contests soo n
motivation is very necessary so if possible then every sunday make a video to how to we study this course and some other knowledge
bhaiya your videos are awesome
bhaiya is recursion series is over or we can expect more videos in this series.
Level increasing day by day 🌠
Lecture 10 Completed ☑
#dsabyfaraz💯
#Recursion 🌠
Consistently at its best,bhaiya
What a explanation. Hat's off to you.
sir your playlist is amazing but please make java related vedios also
Very well explained
Best explanation
Great session maza aaya😌
In the best case it will helps us to ignore all the redundant work which we are doing
Nice explanation bro 🎉
we sorted the array to get all similar elements aligned together and then we just need to add a condition in the recursive function which checks it and skips that occurrence. lec 10 done.
Thanks Buddy for this wonderful explanation
11:55 Fraz, if we sort the given array then we have changed the order of elements in the array. In subsets the main thing to preserve is the order. So, I think we can't sort the array.
Congratulations 🎉🎉👏👏 for upcoming 10k
Day 10 done ✅ tomorrow i will revise all the videos and code from day 1 to day 10 ❤️
Worst case time complexity 2^n
space complexity n
order of consistency is constant😊😊
#bhaiya
Bhaiya beginners course kab se start hogi ??
Will the additional while loop of skipping elements, not add to the time complexity?
Thank you bhiya well explained
Bhaiya in this question the array need to be sorted na ? 🤔 isn’t it possible to do it in O(n) if array is not sorted ? Maybe it’s possible to do it using hash set
hash set wont work here .It will give error. I will explain with an example here.
For eg take an array=[5,5,3,5].
If you run the program using hash set it will produce an output =
3
3 5
5
5 3
5 3 5
5 5
5 5 3
5 5 3 5
5 5 5
If you run the program using vector it will produce the output =
5 5 3 5
5 5 3
5 5 5
5 5
5 3 5
5 3
5 5
5
5 3 5
5 3
5 5
5
3 5
3
5
Now if you observe them carefully set considers those two subsets equal or duplicate if they have same element in the same index or position.
But according to the question they are taking those subsets as equal who have same elements irrespective of their position or indexes.
i.e according to the question [3,5] and [5,3] are also equal. But set doesnt remove them.
Therefore the original output for array=[5,5,3,5] is =
3
3 5
3 5 5
3 5 5 5
5
5 5
5 5 5
2^n to vese bhi lagna hi he recursion me to baki chize nahi sochna or set unique value store karta he to for ex -->3 9 2 3 7 --> isme hame subset k form me (2 3 3 7 9) to chahiye hi set k use se dusra vala 3 lost ho jayega or qn me bola he unique chahiye (2 3 3 7 9) or ye unique he ------>hame duplicate ko count me nahi lena he qn ye bola he-
Episode 10 Done!!🔥
Amazing Explaination ❤️
Subset II:-
(When all the elements inside array/string are not unique)
When we are arent picking the element that to be present inside the subset then make sure that you dont pick the other occurrence of the element we aren't picked,so we need increment i to skip the repeating elements.And to this we use while loop.This is the only difference between Subset I and II
Day 10 done ✅✅
Well going ❤️
This helped a lot! Thanks!
Done understood ❤️✅
Bro, I had a small doubt. Why we need to increment i in the skip part only, why won't before the include part ?
#ep_10 done√√
Love u bhaiya❤️❤️❤️
Thankyou so much!
Thanks sir 😀😀❤️
Ep 10 done ✅.Exam khatam ho geya aj ,ab revision Dena parega achhe se.
Good Video
made me subscribe at 5:38
We can also remove duplicates(set) and create subset
Need to check time complexity for it
can you please explain me why are we skipping duplicate values only in the case of ignoring the element?
what if we convert the given array to set and then back to array and then continue with the same approach as in ep 7, wouldn't that work as well?
Present ! ✔🙌
Completed 👍
Sir what if we can create a discord server for all the information and discussion/doubts
legend!
can u pls explain the same code in java? i saw ur repository, there is no code in java for this problem
Thankyou🌺
Great
that's dope, ty sm!!
find my recursive code if string w/ duplicate char but consecutively is given
public class Recursion{
public static void main(String[] args) {
System.out.println(subSetsWithDupInString("122", ""));
}
static ArrayList subSetsWithDupInString(String str, String ans){
if(str.isEmpty()){
ArrayList ls = new ArrayList();
ls.add(ans);
return ls;
}
char ch = str.charAt(0);
ArrayList left = new ArrayList();
ArrayList right = new ArrayList();
int i = 1;
while(i
thanku
Worst case is when all elements are unique. And the best case is when all elements are same. Then we'll skip all the elements and hence time complexity will be no. Of elements permutated.
Day 10 done,
If elements are unique we need to skip the elements by doing while(i+1 < arr.length && arr[i] == arr[i+1]) and then we need to start the recursion from i+1
thanks a lot
Day 10 completed waiting for tomorrow.
Present ☀️🌻
Why not just use a set to discard dupli at beginning? Can't we do this bhaiya?
Complete Day 10 ❤️
Can't we just use set like we did for unique permutations??
Notes:
The question is very much similar to subset 1 problem, the trick is to figure out the logic that a number should not be included in the subset ever once it is skippped.
Time Complexity: O(2^n) when all elements are unique
Space Complexity: O(n) For recursion stack, not including space taken up by result array
Watched episode 10!
Please try to make 2 videos a day bro
Day 10 how's the Josh...high sir🔥🔥
Episode-10 Done
Time Complexity will be O(2^n) and O(n)
Bhaiya please increase voice quality..very low sound is there
thank you
We can also solve this question using bitmasking. This is the code :-
#include
vector uniqueSubsets(int n, vector &arr)
{
// Write your code here.
sort(arr.begin(),arr.end());
set set_ans;
long long bit_length=(1
How to sort 2D ArrayList??
DAY 10 🔥🔥
summary : earlier we were considering one element and skipping one element but in order to find unique subsets we need skip not only ith element but also all i+1 elements if arr[i]==arr[i+1].
Bhaiya aap sbhi topic cover kroge na DSA ke??
Bhaiya will cover recursion,backtracking,dp,graph,tree in this series and parallel se ek aur series aane wala hai beginner course usme baki topic cover honge.
Very informative and well explained video @LeadCodingbyFRAZ. I came here to checkout the most optimised solution for this problem although I have already solved it using 2 methods. Sharing them here just in case anyone is curious :)
Solution 1 (Using map to store the subsets as it only stores unique values [NOTE : only map works for this and not unordered_map if someone knows why then please do let me know]):
#include
map mp;
void helper(int index,int n,const vector& a,vector& curr){
if(index > n){
mp[curr]++;
return;
}
//include
curr.push_back(a[index]);
helper(index + 1,n,a,curr);
curr.pop_back();
//exclude
helper(index + 1,n,a,curr);
}
vector uniqueSubsets(int n, vector &arr)
{
vector ans;
vector curr;
sort(arr.begin(),arr.end());
helper(0,n - 1,arr,curr);
for(auto& it: mp){
vector x = it.first;
ans.push_back(x);
}
mp.clear();
return ans;
}
Solution 2 (Finding out all the possible subsets and then removing the duplicates using unique( ) ) :
#include
void helper(int index,int n,const vector& a,vector& curr,vector& ans){
if(index > n){
ans.push_back(curr);
return;
}
//include
curr.push_back(a[index]);
helper(index + 1,n,a,curr,ans);
curr.pop_back();
//exclude
helper(index + 1,n,a,curr,ans);
}
vector uniqueSubsets(int n, vector &arr)
{
vector ans;
vector curr;
vector a = arr;
sort(a.begin(),a.end());
helper(0,n - 1,a,curr,ans);
sort(ans.begin(),ans.end());
auto it = unique(ans.begin(),ans.end());
ans.erase(it,ans.end());
return ans;
}
Solution 3 (The most optimised one):
Provided in this video :)
First comment😊
#Day_10
Worst Case Time Complexity is O(2^n)
Space Complexity is O(n)
Consistency OP 🔥🔥🔥
L-10 completed waitng for L-11
Consistency ++