I’m not well guys. Having high fever. Apologies if there is any issue in the quality of audio, video or the content. Hope you all will understand ❤🙏🏻 Few small NOTES - 1) Also note that, mp.find(nums[idx] - K)) checks the existence but mp[nums[idx]-K) will check frequency. Since we have to check frequency, that's why I used mp[nums[idx] - k) and putting a Not operator(!) behind helps to confirm that it's frequency is 0. One alternate thing you can do is, when you do the "Undo" step in bakctracking (mp[nums[idx]]--), check if mp[nums[idx]] has become 0, then you can remove it from map) and then you can use mp.find() 2) You can't use set/unordered_set because we can have duplicate elements too in the nums.
If anyone is wondering why taking an unordered_set will give wrong result but unordered_map will give correct result. Actually this could be figured out easily with a small example : The intuition can be explained with this small example : [6,4,6], k = 2 Suppose you took 6 (idx = 0) , set = {6} and now you move further to explore this path. Now, you can't take 4 because 4+k is present in set. Then you move to 6 (idx = 2), you can take it. your subset becomes = 6,6 and your set = {6} --- NOTE that set only contains unique element so even if you input 6 of idx=2, the set only contains one instance of 6 Since you have explored this path, you will remove 6 from your set. now your set is = {} Now, when you explore taking 4, you will see that your set doesn't contain 4+k i.e. 6 because there was only one instance of 6 and you deleted that. Here we will go wrong. So the intuition is basically to keep the exact count of occurrences of elements in the map so that you don't miss any element you have taken for your subset.
MikBhai, tumhra dedication gives me more motivation!! Tum bhai thoda rest le koi baat nahi. tum jaab vi video dega dekhenge. with all respect Love you brother! although I solved it using backtracking which i learnt from you. thank you Mik.. jai coding❤
Hi get well soon. Thanks for the explanation. But need all other approaches. Hope it will be in future. here is java code for this question:- class Solution { public int K=0; public int beautifulSubsets(int[] nums, int k) { HashMap map=new HashMap(); helper(0,nums,map,k); return K; } public void helper(int idx,int nums[],HashMap map,int k){ if(idx==nums.length){ if(map.size()!=0)K++; return; } if(!map.containsKey(nums[idx]+k) && !map.containsKey(nums[idx]-k)){ if(map.containsKey(nums[idx]))map.put(nums[idx],map.get(nums[idx])+1); else map.put(nums[idx],1); helper(idx+1,nums,map,k); map.put(nums[idx],map.get(nums[idx])-1); if(map.get(nums[idx])==0)map.remove(nums[idx]); } helper(idx+1,nums,map,k); return; } }
I hope sir apki tabiyat jldi theek ho jaye… jaise hee theek ho jaoo toe sir trees ki playlist le ana concept wali aur dp series complete kara dena… get well soon sir 🙏🏻🙏🏻🙏🏻
i am using set to solve this question in the same manner but after passing 1302 out of 1307 test case it gives wrong answer. here you using map for checking the element is previously appear or not .we can also use the set for doing the same operation
class Solution { public int beautifulSubsets(int[] nums, int k) { int n=nums.length; int result[]={0}; HashSet set=new HashSet(); find(nums,n,result,0,set,k); return result[0]-1; } public void find(int nums[],int n,int result[],int ind,HashSet set,int k){ if(ind==n){ result[0]++; return; } // not take find(nums,n,result,ind+1,set,k); // take if no overlapping if(!set.contains(nums[ind]-k) && !set.contains(nums[ind]+k)){ set.add(nums[ind]); find(nums,n,result,ind+1,set,k); set.remove(nums[ind]); } } } why is it failing for last few test cases
what was ur thought process for taking map instead of taking set. i first use set then realise that numbers can be repetitive after seeing wrong ans. was able to do it myself
That's a good Qn. The intuition can be explained with this small example : [6,4,6], k = 2 Suppose you took 6 (idx = 0) , set = {6} and now you move further to explore this path. Now, you can't take 4 because 4+k is present in set. Then you move to 6 (idx = 2), you can take it. your subset becomes = 6,6 and your set = {6} --- NOTE that set only contains unique element so even if you input 6 of idx=2, the set only contains one instance of 6 Since you have explored this path, you will remove 6 from your set. now your set is = {} Now, when you explore taking 4, you will see that your set doesn't contain 4+k i.e. 6 because there was only one instance of 6 and you deleted that. Here we will go wrong. So the intuition is basically to keep the exact count of occurrences of elements in the map so that you don't miss any element you have taken for your subset.
i have a doubt why haven't we took a hashset why we use only hashmap when in set we can find the contains element in O(1) and this is much easy to understand rather than increasing the value and then decreasing we can just add to set and remove from set isn't that easy ?
If anyone is wondering why taking an unordered_set will give wrong result but unordered_map will give correct result. Actually this could be figured out easily with a small example : The intuition can be explained with this small example : [6,4,6], k = 2 Suppose you took 6 (idx = 0) , set = {6} and now you move further to explore this path. Now, you can't take 4 because 4+k is present in set. Then you move to 6 (idx = 2), you can take it. your subset becomes = 6,6 and your set = {6} --- NOTE that set only contains unique element so even if you input 6 of idx=2, the set only contains one instance of 6 Since you have explored this path, you will remove 6 from your set. now your set is = {} Now, when you explore taking 4, you will see that your set doesn't contain 4+k i.e. 6 because there was only one instance of 6 and you deleted that. Here we will go wrong. So the intuition is basically to keep the exact count of occurrences of elements in the map so that you don't miss any element you have taken for your subset.
I had a small doubt , why this line of code works find if (!mp[nums[index]-k] && !mp[nums[index]+k]) but this one doesn't if ((mp.find(nums[index] - k) == mp.end() && mp.find(nums[index] + k) == mp.end())) Can anyone help please
Bhai, if you notice we are reducing the frequency of mp (in undo step), so the element will be there in the map but with zero frequency. So, we must check frequency of mp[nums[idx] - K] instead of mp.find(nums[idx] - K)
You are incrementing mp[nums[idx]]++ and for undoing mp[nums[idx]]-- cant we do mp[nums[idx]] = 1 and mp[nums[idx]] = 0 ? and when submitting this 1 and 0 approach i am getting error so why this is not good as i am setting the mp[nums[idx]] as 1 to indicate that it is there?
What you are doing is similar to using a set/unordered_set instead of map. 1 means it's present in set and 0 means, it's not present. But let me tell you why this is wrong The intuition can be explained with this small example : [6,4,6], k = 2 Suppose you took 6 (idx = 0) , set = {6} and now you move further to explore this path. Now, you can't take 4 because 4+k is present in set. Then you move to 6 (idx = 2), you can take it. your subset becomes = 6,6 and your set = {6} --- NOTE that set only contains unique element so even if you input 6 of idx=2, the set only contains one instance of 6 Since you have explored this path, you will remove 6 from your set. now your set is = {} Now, when you explore taking 4, you will see that your set doesn't contain 4+k i.e. 6 because there was only one instance of 6 and you deleted that. Here we will go wrong. So the intuition is basically to keep the exact count of occurrences of elements in the map so that you don't miss any element you have taken for your subset.
class Solution { public: void rec(int &res, vector &nums, vector &count, int i, int k) { if (i == nums.size()) { res++; return; } // can we count this number if yes then call rec() accordingly // note if nums[i] < k then count[] can not have that value so its okay to include nums[i] in that case if (nums[i] < k || count[nums[i] - k] == 0) { count[nums[i]]++; rec(res, nums, count, i+1, k); count[nums[i]]--; } // we just rec() without counting this number. rec(res, nums, count ,i +1, k); } int beautifulSubsets(vector& nums, int k) { sort(nums.begin(), nums.end()); vector count(1001, 0); vector s; int res=0; rec(res, nums, count, 0, k); return res-1; // subtract 1 as we don't want to count empty set. } }; Here I have done it with using vector instead of map to count freq. Which works but just want to make sure if this is correct, specially condition if (nums[i] < k || count[nums[i] - k] == 0) {
class Solution { public int beautifulSubsets(int[] nums, int k) { List res=new ArrayList(); List l=new ArrayList(); solve(nums,k,0,l,res); int c=0; Iterator iterator = res.iterator(); while (iterator.hasNext()) { List x = iterator.next();//removing the empty susbets from res if (x.isEmpty()) { iterator.remove(); }} for(List x:res) { if(beau(x,k)) { c++; } } return c; } public boolean beau(Listx,int k) { Collections.sort(x); if(x.size()==1) { return true; } for(int i=0;i=nums.length) { res.add(new ArrayList(l)); return; } l.add(nums[idx]); solve(nums,k,idx+1,l,res); l.remove(l.size()-1); solve(nums,k,idx+1,l,res); } } I WROTE THE CODE BUT ONLY 1135/1307 PASSING can anyone check basically i am generating subsets and then counting the beautidul subsets
If anyone is wondering why taking an unordered_set will give wrong result but unordered_map will give correct result. Actually this could be figured out easily with a small example : The intuition can be explained with this small example : [6,4,6], k = 2 Suppose you took 6 (idx = 0) , set = {6} and now you move further to explore this path. Now, you can't take 4 because 4+k is present in set. Then you move to 6 (idx = 2), you can take it. your subset becomes = 6,6 and your set = {6} --- NOTE that set only contains unique element so even if you input 6 of idx=2, the set only contains one instance of 6 Since you have explored this path, you will remove 6 from your set. now your set is = {} Now, when you explore taking 4, you will see that your set doesn't contain 4+k i.e. 6 because there was only one instance of 6 and you deleted that. Here we will go wrong. So the intuition is basically to keep the exact count of occurrences of elements in the map so that you don't miss any element you have taken for your subset.
can anyone tell ki MAP ki jgeh set lene s kya issue aa rha hai ??? class Solution { public int beautifulSubsets(int[] nums, int k) {
// find subset and maintain count int count = 0; Setset = new HashSet(); return help(nums,set,k,0) - 1; // -1 to exclude empty subset } public int help(int[] nums,Setset, int k,int index) { if(index == nums.length) { return 1; } int ans = 0; // not take ans += help(nums,set,k,index+1);
// take when diff element is not present if((!set.contains(nums[index]-k)) && (!set.contains(nums[index]+k))) { set.add(nums[index]); ans+= help(nums,set,k,index+1); set.remove(nums[index]); } return ans; } }
If anyone is wondering why taking an unordered_set will give wrong result but unordered_map will give correct result. Actually this could be figured out easily with a small example : The intuition can be explained with this small example : [6,4,6], k = 2 Suppose you took 6 (idx = 0) , set = {6} and now you move further to explore this path. Now, you can't take 4 because 4+k is present in set. Then you move to 6 (idx = 2), you can take it. your subset becomes = 6,6 and your set = {6} --- NOTE that set only contains unique element so even if you input 6 of idx=2, the set only contains one instance of 6 Since you have explored this path, you will remove 6 from your set. now your set is = {} Now, when you explore taking 4, you will see that your set doesn't contain 4+k i.e. 6 because there was only one instance of 6 and you deleted that. Here we will go wrong. So the intuition is basically to keep the exact count of occurrences of elements in the map so that you don't miss any element you have taken for your subset.
WHY IS THIS NOT WORKING class Solution { public: void solve(int ind,vector&nums,int k, int &ans, unordered_map&mpp){ if(ind==nums.size()){ ans++; return; } if(mpp.find(nums[ind]-k)==mpp.end() && mpp.find(nums[ind]+k)==mpp.end() ){ // we can choose this mpp[nums[ind]]++; solve(ind+1,nums,k,ans,mpp); mpp[nums[ind]]--; } // not taking this solve(ind+1,nums,k,ans,mpp);
} int beautifulSubsets(vector& nums, int k) { int ans=0; unordered_mapmpp; solve(0,nums,k,ans,mpp); return ans-1; } };
I’m not well guys. Having high fever. Apologies if there is any issue in the quality of audio, video or the content. Hope you all will understand ❤🙏🏻
Few small NOTES -
1) Also note that, mp.find(nums[idx] - K)) checks the existence but mp[nums[idx]-K) will check frequency. Since we have to check frequency, that's why I used mp[nums[idx] - k) and putting a Not operator(!) behind helps to confirm that it's frequency is 0. One alternate thing you can do is, when you do the "Undo" step in bakctracking (mp[nums[idx]]--), check if mp[nums[idx]] has become 0, then you can remove it from map) and then you can use mp.find()
2) You can't use set/unordered_set because we can have duplicate elements too in the nums.
Take care mik
Take care your health
take care
taka care
take care mik.
your dedication will not go unnoticed man. please take care
If anyone is wondering why taking an unordered_set will give wrong result but unordered_map will give correct result. Actually this could be figured out easily with a small example :
The intuition can be explained with this small example :
[6,4,6], k = 2
Suppose you took 6 (idx = 0) , set = {6} and now you move further to explore this path.
Now, you can't take 4 because 4+k is present in set.
Then you move to 6 (idx = 2), you can take it. your subset becomes = 6,6 and your set = {6} --- NOTE that set only contains unique element so even if you input 6 of idx=2, the set only contains one instance of 6
Since you have explored this path, you will remove 6 from your set. now your set is = {}
Now, when you explore taking 4, you will see that your set doesn't contain 4+k i.e. 6 because there was only one instance of 6 and you deleted that. Here we will go wrong.
So the intuition is basically to keep the exact count of occurrences of elements in the map so that you don't miss any element you have taken for your subset.
Thanks bro to explain it so well, I was actually doing it using set and was confused why is it failing.
I got the reason now I can sleep peacefully :)
Thanks
Thanks and wishing for your fast health recovery 😊.
The only person who genuinely makes questions so easy to understand. Get well soon brother!!
Dear DSA GOD wishing U for Ur Speedy recovery
MikBhai, tumhra dedication gives me more motivation!! Tum bhai thoda rest le koi baat nahi. tum jaab vi video dega dekhenge. with all respect Love you brother! although I solved it using backtracking which i learnt from you. thank you Mik.. jai coding❤
*tumhra *tum
you respectable words
@@bhuppidhamii waise kuch intention nahi tha. you point it out. abhi fix kar deta hu.
@@bhuppidhamii are koi baat nahi bhai. I don't think aisa koi intention raha hoga . But it's ok. respect for all.
@@spdh6325 Thank you 🤗
@@gui-codes yes 😊
you are a legend. please take care
I could solve this Qn in 5-6 minutes. so happy
Take care sir!! Get well soon! Thank you for your consistent efforts daily! A lot to learn from you! 🙏
I was able to solve it on my own. But it’s all because of your precious backtracking videos. Please take care legend. You take rest
thanks bhaiya , i make this Question by own without seeing your this viedo , Dil se thanks🙂
Take care brother, get well soon.
Thanks a lot bhaiya ❤❤ Hats off to your dedication. Get well soon 🙌❤.
Hi get well soon. Thanks for the explanation. But need all other approaches. Hope it will be in future.
here is java code for this question:-
class Solution {
public int K=0;
public int beautifulSubsets(int[] nums, int k) {
HashMap map=new HashMap();
helper(0,nums,map,k);
return K;
}
public void helper(int idx,int nums[],HashMap map,int k){
if(idx==nums.length){
if(map.size()!=0)K++;
return;
}
if(!map.containsKey(nums[idx]+k) && !map.containsKey(nums[idx]-k)){
if(map.containsKey(nums[idx]))map.put(nums[idx],map.get(nums[idx])+1);
else map.put(nums[idx],1);
helper(idx+1,nums,map,k);
map.put(nums[idx],map.get(nums[idx])-1);
if(map.get(nums[idx])==0)map.remove(nums[idx]);
}
helper(idx+1,nums,map,k);
return;
}
}
Get well soon, brother
Take care sir. you are already doing a lot for us. 💗
I hope sir apki tabiyat jldi theek ho jaye… jaise hee theek ho jaoo toe sir trees ki playlist le ana concept wali aur dp series complete kara dena… get well soon sir 🙏🏻🙏🏻🙏🏻
Please take care of ur health. Get well soon brother✌🏻
sir, how to get this kind of dedication in life?
sir get well soon ❤
When using mp.find() we have to erase it also if mp[val] == 0 while backtracking. I used this method but it gave memory limit exceeded. Why?
get well soon bhai
Get well soon!
Thank uh✨.Take Care
take care sir ji 🙌
Just a suggestion, please upload other approaches as well, whenever you feel good. Get well soon
Get well soon 🤝
There is a dp solution for this, is it possible for you to post that once you are well! Bdw your videos are lit!
Take care brother ❤
Sir aap ney apne channel pey jitne backtracking key questions kaarey hai sabko ekk hi playlist mey dal dijiye 🙏🙏
I can see Backtracking playlist in his channel. Search Backtracking in his channel
take care...
In the Follow up they says to solve in N logN time
Take care Sir !!
i am using set to solve this question in the same manner but after passing 1302 out of 1307 test case it gives wrong answer. here you using map for checking the element is previously appear or not .we can also use the set for doing the same operation
No you can’t. The nums can have duplicate elements too.
Try this example - {6, 4, 6} , K = 2
class Solution {
public int beautifulSubsets(int[] nums, int k) {
int n=nums.length;
int result[]={0};
HashSet set=new HashSet();
find(nums,n,result,0,set,k);
return result[0]-1;
}
public void find(int nums[],int n,int result[],int ind,HashSet set,int k){
if(ind==n){
result[0]++;
return;
}
// not take
find(nums,n,result,ind+1,set,k);
// take if no overlapping
if(!set.contains(nums[ind]-k) && !set.contains(nums[ind]+k)){
set.add(nums[ind]);
find(nums,n,result,ind+1,set,k);
set.remove(nums[ind]);
}
}
} why is it failing for last few test cases
get well soon
what was ur thought process for taking map instead of taking set.
i first use set then realise that numbers can be repetitive after seeing wrong ans.
was able to do it myself
That's a good Qn. The intuition can be explained with this small example :
[6,4,6], k = 2
Suppose you took 6 (idx = 0) , set = {6} and now you move further to explore this path.
Now, you can't take 4 because 4+k is present in set.
Then you move to 6 (idx = 2), you can take it. your subset becomes = 6,6 and your set = {6} --- NOTE that set only contains unique element so even if you input 6 of idx=2, the set only contains one instance of 6
Since you have explored this path, you will remove 6 from your set. now your set is = {}
Now, when you explore taking 4, you will see that your set doesn't contain 4+k i.e. 6 because there was only one instance of 6 and you deleted that. Here we will go wrong.
So the intuition is basically to keep the exact count of occurrences of elements in the map so that you don't miss any element you have taken for your subset.
how can we do this question the loop method of backtacking?
Sir, backtracking approach is valid for very low constraints due to time complexity of O(2^n)
yes. this seems to be a pure backtracking problem due to constraints
Take Care < 3!
take care legend
Thank you bhaiya❤
take care sirr❤
Day-2 of asking "How do you manage teaching DSA, Office Hours, Doing sports as well as travel and handling social media" 😅
i have a doubt why haven't we took a hashset
why we use only hashmap when in set we can find the contains element in O(1) and this is much easy to understand rather than increasing the value and then decreasing we can just add to set and remove from set isn't that easy ?
If anyone is wondering why taking an unordered_set will give wrong result but unordered_map will give correct result. Actually this could be figured out easily with a small example :
The intuition can be explained with this small example :
[6,4,6], k = 2
Suppose you took 6 (idx = 0) , set = {6} and now you move further to explore this path.
Now, you can't take 4 because 4+k is present in set.
Then you move to 6 (idx = 2), you can take it. your subset becomes = 6,6 and your set = {6} --- NOTE that set only contains unique element so even if you input 6 of idx=2, the set only contains one instance of 6
Since you have explored this path, you will remove 6 from your set. now your set is = {}
Now, when you explore taking 4, you will see that your set doesn't contain 4+k i.e. 6 because there was only one instance of 6 and you deleted that. Here we will go wrong.
So the intuition is basically to keep the exact count of occurrences of elements in the map so that you don't miss any element you have taken for your subset.
Legend 🔥
I had a small doubt , why this line of code works find if (!mp[nums[index]-k] && !mp[nums[index]+k]) but this one doesn't if ((mp.find(nums[index] - k) == mp.end() && mp.find(nums[index] + k) == mp.end())) Can anyone help please
Bhai, if you notice we are reducing the frequency of mp (in undo step), so the element will be there in the map but with zero frequency. So, we must check frequency of mp[nums[idx] - K] instead of mp.find(nums[idx] - K)
@@gui-codes Got it , thanks a lot brother 🙌
@@gauravbanerjee2898 ❣
class Solution {
public:
int cal(int i, vector &nums, int k, unordered_map &mp) {
if (i == nums.size()) {
return 1;
}
int t = 0;
if (mp[nums[i] - k] == 0) {
mp[nums[i]]++;
t = cal(i + 1, nums, k, mp);
mp[nums[i]]--;
}
int nt = cal(i + 1, nums, k, mp);
return t + nt;
}
int beautifulSubsets(vector& nums, int k) {
sort(nums.begin(), nums.end());
unordered_map mp;
return cal(0, nums, k, mp) - 1;
}
};
I solved exactly like this. cool
can we use unrodered_set instead of unordered_map
No you can’t. The nums can have duplicate elements too.
Try this example - {6, 4, 6} , K = 2
You are incrementing mp[nums[idx]]++ and for undoing mp[nums[idx]]-- cant we do mp[nums[idx]] = 1 and mp[nums[idx]] = 0 ? and when submitting this 1 and 0 approach i am getting error so why this is not good as i am setting the mp[nums[idx]] as 1 to indicate that it is there?
What you are doing is similar to using a set/unordered_set instead of map. 1 means it's present in set and 0 means, it's not present. But let me tell you why this is wrong
The intuition can be explained with this small example :
[6,4,6], k = 2
Suppose you took 6 (idx = 0) , set = {6} and now you move further to explore this path.
Now, you can't take 4 because 4+k is present in set.
Then you move to 6 (idx = 2), you can take it. your subset becomes = 6,6 and your set = {6} --- NOTE that set only contains unique element so even if you input 6 of idx=2, the set only contains one instance of 6
Since you have explored this path, you will remove 6 from your set. now your set is = {}
Now, when you explore taking 4, you will see that your set doesn't contain 4+k i.e. 6 because there was only one instance of 6 and you deleted that. Here we will go wrong.
So the intuition is basically to keep the exact count of occurrences of elements in the map so that you don't miss any element you have taken for your subset.
easy ❌❌ super easy✅✅
class Solution {
public:
void rec(int &res, vector &nums, vector &count, int i, int k) {
if (i == nums.size()) {
res++;
return;
}
// can we count this number if yes then call rec() accordingly
// note if nums[i] < k then count[] can not have that value so its okay to include nums[i] in that case
if (nums[i] < k || count[nums[i] - k] == 0) {
count[nums[i]]++;
rec(res, nums, count, i+1, k);
count[nums[i]]--;
}
// we just rec() without counting this number.
rec(res, nums, count ,i +1, k);
}
int beautifulSubsets(vector& nums, int k) {
sort(nums.begin(), nums.end());
vector count(1001, 0);
vector s;
int res=0;
rec(res, nums, count, 0, k);
return res-1; // subtract 1 as we don't want to count empty set.
}
};
Here I have done it with using vector instead of map to count freq. Which works but just want to make sure if this is correct, specially condition if (nums[i] < k || count[nums[i] - k] == 0) {
this is a good approach. you are using the benefit of constraint 1
@@gui-codes I see makes more sense now. Thanks!
sadly, I was not able to do it myself😓
class Solution {
public int beautifulSubsets(int[] nums, int k) {
List res=new ArrayList();
List l=new ArrayList();
solve(nums,k,0,l,res);
int c=0;
Iterator iterator = res.iterator();
while (iterator.hasNext()) {
List x = iterator.next();//removing the empty susbets from res
if (x.isEmpty()) {
iterator.remove();
}}
for(List x:res)
{
if(beau(x,k))
{
c++;
}
}
return c;
}
public boolean beau(Listx,int k)
{
Collections.sort(x);
if(x.size()==1)
{
return true;
}
for(int i=0;i=nums.length)
{
res.add(new ArrayList(l));
return;
}
l.add(nums[idx]);
solve(nums,k,idx+1,l,res);
l.remove(l.size()-1);
solve(nums,k,idx+1,l,res);
}
}
I WROTE THE CODE BUT ONLY 1135/1307 PASSING can anyone check basically i am generating subsets and then counting the beautidul subsets
Sir can we use hashset instead of hashmap
If anyone is wondering why taking an unordered_set will give wrong result but unordered_map will give correct result. Actually this could be figured out easily with a small example :
The intuition can be explained with this small example :
[6,4,6], k = 2
Suppose you took 6 (idx = 0) , set = {6} and now you move further to explore this path.
Now, you can't take 4 because 4+k is present in set.
Then you move to 6 (idx = 2), you can take it. your subset becomes = 6,6 and your set = {6} --- NOTE that set only contains unique element so even if you input 6 of idx=2, the set only contains one instance of 6
Since you have explored this path, you will remove 6 from your set. now your set is = {}
Now, when you explore taking 4, you will see that your set doesn't contain 4+k i.e. 6 because there was only one instance of 6 and you deleted that. Here we will go wrong.
So the intuition is basically to keep the exact count of occurrences of elements in the map so that you don't miss any element you have taken for your subset.
Take care
78. Subset II video
take care bhai
can anyone tell ki MAP ki jgeh set lene s kya issue aa rha hai ???
class Solution {
public int beautifulSubsets(int[] nums, int k) {
// find subset and maintain count
int count = 0;
Setset = new HashSet();
return help(nums,set,k,0) - 1; // -1 to exclude empty subset
}
public int help(int[] nums,Setset, int k,int index)
{
if(index == nums.length)
{
return 1;
}
int ans = 0;
// not take
ans += help(nums,set,k,index+1);
// take when diff element is not present
if((!set.contains(nums[index]-k)) && (!set.contains(nums[index]+k)))
{
set.add(nums[index]);
ans+= help(nums,set,k,index+1);
set.remove(nums[index]);
}
return ans;
}
}
If anyone is wondering why taking an unordered_set will give wrong result but unordered_map will give correct result. Actually this could be figured out easily with a small example :
The intuition can be explained with this small example :
[6,4,6], k = 2
Suppose you took 6 (idx = 0) , set = {6} and now you move further to explore this path.
Now, you can't take 4 because 4+k is present in set.
Then you move to 6 (idx = 2), you can take it. your subset becomes = 6,6 and your set = {6} --- NOTE that set only contains unique element so even if you input 6 of idx=2, the set only contains one instance of 6
Since you have explored this path, you will remove 6 from your set. now your set is = {}
Now, when you explore taking 4, you will see that your set doesn't contain 4+k i.e. 6 because there was only one instance of 6 and you deleted that. Here we will go wrong.
So the intuition is basically to keep the exact count of occurrences of elements in the map so that you don't miss any element you have taken for your subset.
@@gui-codes thanks vro
@@abcd76820 ❣
khaandani template toh hai 🤣
❤❤
Itni mehnat karte ho sir. thoda rest lelo. take care
WHY IS THIS NOT WORKING
class Solution {
public:
void solve(int ind,vector&nums,int k, int &ans, unordered_map&mpp){
if(ind==nums.size()){
ans++;
return;
}
if(mpp.find(nums[ind]-k)==mpp.end() && mpp.find(nums[ind]+k)==mpp.end() ){
// we can choose this
mpp[nums[ind]]++;
solve(ind+1,nums,k,ans,mpp);
mpp[nums[ind]]--;
}
// not taking this
solve(ind+1,nums,k,ans,mpp);
}
int beautifulSubsets(vector& nums, int k) {
int ans=0;
unordered_mapmpp;
solve(0,nums,k,ans,mpp);
return ans-1;
}
};
What is your LeetCode username?