L12. Print all Permutations of a String/Array | Recursion | Approach - 1
Vložit
- čas přidán 7. 03. 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
---------------------------------------------------------------------------------------------------------------------------------------------------- I have decided to make a free placement series comprising of video lectures(C++ and Java) on the entire SDE sheet.. ✅(bit.ly/takeUforward_SDE)
✅Entire Series: bit.ly/placementSeries
✅Problem Link: leetcode.com/problems/permuta...
C++/Java Code: takeuforward.org/data-structu...
Access all the Free Live Classes here: unacademy.cc/daily_learning
Batch for Beginners starting 8th March (Check Course plan) : bit.ly/beginnerbatch
Batch for Intermediates started 4th March: bit.ly/batchascend
Free Test (Exciting prizes for Winners): bit.ly/deadheattest
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_cpCourse
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgCourse
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: / rajarvp
✅ Instagram: / striver_79
Connect with us: t.me/Competitive_Programming_tuf (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #leetcode #placements
it's very rare to find such explanations of recursion! Striver and Aditya Verma both are the best when it comes to recursion! Thanks for making recursion easy :)
Yaar dono hi aiseee.... tree method se padhayenge na ?
Bas iye bta do
@@sayantaniguha8519 yes
you shoud chack kunal kuswaha recursion.
@@puspendragaming6352 He isn't that good. I honestly understood from Striver more than Kunal a thousand times;
Striver is best
ATTENTION
Are you wondering, why it is ans.add(new ArrayList(ds)); instead of ans.add(ds);
If you are using ans.add(ds); ds is passed as shallow copy.. the lists will be added to ans appropriately
BUT as we remove the elements from the list ds since it is a shallow copy it will also be reflected in ans list
Hope this made sense😁
This is something we don't see in cpp. Due to which many new java users get confused by it. Thanks for this clear explanation
Thanks alot bro........
didn't understand? shallow copy is mentioning the same list with different reference, i.e both are dependent, if you modify one , it will be reflected in other reference also, because of using same list, just different referencing!
FOR THOSE, who are not getting "Why we are removing the last element after the recursive call ?". Objects like (Arrays, Maps, Custom class objects etc- all objects) in most programming languages are passed by reference in the function call unlike plain variables (int, char etc), so when you are passing the list/array to the recursive call, any updation(add/remove) on the object will be retained even after the function call finishes. Since for the right/other subtrees (of recursion call) we are not considering the same element. So we need to remove it explicitly.
If you would have passed the new replica/instance of the data structure in every recursive call, then this was not required. Hope this clears the doubt.
Is string also passed by reference in c++??
@@nirnayjain7097 ya
nope ur wrong in c++ vectors are not passed by refrence arrays are. So in this code u can omit the popback function if u dont pass the vector by reference but in order to improve upon the space complexity it is better to pass the vector by reference hence the use of the pop function
@@codingachinilgtifirbhikrrh9009 I am generalising here, not talking of any specific programming language.
@@codingachinilgtifirbhikrrh9009 The pop function has to be included regardless since we have a for loop we don't want ds from the previous iteration to reflect in the next. We could have omitted the reference for ds though but no point in doing that since we need to save up some space.
very well understood, Initially i was not able to solve recursion ,Dynamic programming problem.But now i am able to do that all , by just following your playlist.
Great explanation. U r the lord of Data structure and Algorithm. I sometimes wonder how you understand recursion so beautifully. This is not my cup of tea, if you are not there. Your channel is helping me a lot in understanding advance topics of DSA. I will always be thankful to you
faced many difficulties when i am following another source for recursion but after learning from u now I am clear with recursion questions and also able to solve this question myself in 10 minutes thanks striver for the amazing content......
ur explanation had taken me really forward in understanding this problem as well as recursion, HATS OFF to u and ur work ♥🔥🔥🔥
I came up with the exact 100% logic and code though it took me 3-4 hours but I am so happy that I did solve the problem before looking the approach or the solution all because of the previous problems of the playlist and the beautiful explanation by striver... Though, I could not think of the next approach that is swap, I could only think of the boolean approach
Great Explanation. There is a good connectivity of the concepts which are taught in the earlier videos of this recursion playlist.
The reccursion tree is really helpful thank u bhaiya🙏
Great explaination brother! I am really enjoying this series :) This will never get old ❤❤
Your PlayList for recursion is the best .
insted of creating int freq[nums.size()]={0} make itin vector as vectormap(nums.size(),0);
afterall..... this is the first ever videos through which i grasp my recursion concept, jiyo striver jiyo
Easiest thing on the planet ...
I love recursion
Amazing explanation :) very helpful to understand recursion. I was also thinking in this way but not getting implementation way. thank you so much
Thank you so much brother now I'm able to solve recursions questions and also able to understand the behind of approach in recursion and backtracking
Thank you so much You are amazing man.
the space complexity O(n !) is for the resultant vector. We are not considering that vector because we are not using it to solve our problem but we are using it to store the answer for our problem.
AS for the O(N) + O(N) space, first is used to store the possible values of a single Permutation and the other space is for the Map which stores the frequency of element in the array which is used to check whether we had already taken that element in the current Permutation or not.
Hope it helps!
thanks thanks thanks alot striver I was facing so much issues in undertanding this problem saw other yt video explaination as well (but I couldn't understand their explaination properly ) but u made it very very simple thank you so much for what ever u r doing. Please keep on making such awesome videos bhai.
I hope you are doing extremely well bhaiya ❤️❤️
Love the way you solve each and every problem.
Kudos to you
💯💯💯💯💯
Thank you Raj Brother . elegant explanation with Rec tree.
bestest video I have watched till now for permuataions 🔥🔥
Love the way u explained 🔥🔥
The excel sheet format was super useful.
UNDERSTOOD.......Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
A day to remember me ...when i started ds u r channel is the best
Thank You Striver , Was crystal clear video
Bhai bhai! Maaza aagya.. thanks for such easy explanation.
Thank you for the best explanation
this channel is a gold mine
best explanation of recursion.
Thank you!!!! Nicely explained :)))
Well this can be done in constant space if we just store the character which we are taking in our current permutation in temp variable and change the char by some dummy char or space and recursively call the same function while picking the char ensure that it is not a space. and while doing backtracking we can change the curr char to temp. so that our input string remains same.
Very Nice Explanation !
Great explanation !!!!
Hare Krishna! Thanks Now I can solve the Problem
Understood completely!!
Thanks, Raj you don't know how much you help college students like me. This explanation was mind-blowing.
awesome, you are my best teacher
thank you very much raj bhai
bro wth, this got accepted on the first try without even looking at your pseudocode (beats 100% as well). Amazing work Striver!!!!
What an intutive solution 😍
thank you bhaiya 👍🏼
Thanks Sir for the explanation
Thank you so much.
Thanks sir Understood everything
coded on my own...Thks striver
very good explaination man
Thanks a lot , bhaiya
Understood, thank you.
Thanks Striver !
Awesome explanation
Best Explanation. Backtracking is all about dry running the code. If you know the intuition behind the solving the problem, you will experience magic with backtracking.
Awesome video. Btw, we can reduce space complexity to O(1) by doing a[i] = -1 while including it and again restoring it during backtrack. It will do the same that map is doing but in O(1) time.😊
Yes, we can, but we generally don’t modify the given arr..
@@takeUforward Yeah, got the point! Thank you😁
@@nitigya but it won't work if the array contains negatives as well :\
@@rahulsrivastava1040 OP, in that case we can use Max(arr) + 1 or min(arr) - 1. But yeah, that can overflow if the max/min is upper limit. Your point is really nice.
Thanks man!
your video is one of the best video on youtube but i wish this could be in hindi language then it may be more clear to us
by the way thanks for your effort
Only man who can go par to par with adithya verma on recursion...truly awsome🤯
I have seen both... Striver is much better
Ap great ho bhaiya hmm phele next permutation q krne gaye apki sheet ka vha permutation ki need padi to logic bna hi nahi....😔😔😔
what if the vector nums contains duplicate elements?...this method would print duplicate permutations as well....eg if the vector contains 1,1,2 then the vector ans would contain {1,1,2} , {1,1,2} , {1,2,1} , {1,2,1} , {2,1,1} and {2,1,1}.....how to remove duplicates without using sets?
I faced the same problem. have you found any solution yet?
Just because of you I was able to do this question without even looking for solution and I was able to submit it on LeetCode within less than 20 min.....thnaks bhaiya
///////
void solve(int idx, vector &nums, unordered_map ump, vector &ans, vector list)
{
if (list.size() == nums.size())
{
ans.push_back(list);
return;
}
for (int i = 0; i < nums.size(); ++i)
{
if (ump[nums[i]] == 1)
continue;
list.push_back(nums[i]);
ump[nums[i]] = 1;
solve(i + 1, nums, ump, ans, list);
list.pop_back();
ump[nums[i]] = 0;
}
}
class Solution {
public:
vector permute(vector& nums) {
unordered_mapump;
vectorans;
vectorlist;
solve(0, nums, ump, ans, list);
return ans;
}
};
/////
great video. commenting for more reach
Instead of taking a frequency array of n length we should take a map as it will not work correctly for negative values constraints of leetcode . Thanks a lot for wonderful explanation.
Understood thanks :)
Thank you
Thank you sir
excellent man keep it up
Thank youuuuuu
Nice explanation
Beautiful code ! 👌
In c++ code we do we need vector < vector < int>> permute ( vector & nums)
And this
vector < vector < int>> ans;
Please someone explain
thanks alot
In the previous problems, we were considering time complexity based on no. Of recursion calls and not the for loops, but this time why is it the opposite??
public static void generatePermutations(int[] arr, int index, Map used, StringBuilder sb) {
if (index == arr.length) {
// All elements have been used, so we can print the permutation
System.out.println(sb.toString());
return;
}
// Try using each element in the permutation
for (int i = 0; i < arr.length; i++) {
// Skip elements that have already been used
if (used.get(i)) {
continue;
}
// Mark element as used and append it to the permutation string
used.put(i, true);
sb.append(arr[i]);
// Generate permutations with the updated string
generatePermutations(arr, index + 1, used, sb);
// Backtrack: mark element as unused and remove it from the permutation string
used.put(i, false);
sb.deleteCharAt(sb.length() - 1);
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3};
Map used = new HashMap();
for (int i = 0; i < arr.length; i++) {
used.put(i, false);
}
StringBuilder sb = new StringBuilder();
generatePermutations(arr, 0, used, sb);
}
Approach is good but i have one doubt if there is backtracking so once will return from down to top then will call the next iteration
Awesome!!!!!!!
Please leave a small comment if you understand by spending your time here, every comment motivates me more :)
C++ Code: github.com/striver79/SDESheet/blob/main/permutationsCppApproach-1
Java Code: github.com/striver79/SDESheet/blob/main/permutationsJavaApproach-1
Approach-2 Video Link: czcams.com/video/f2ic2Rsc9pU/video.html
Instagram(For live sessions): instagram.com/striver_79/
Hi!!
1 question, why we are using ds.remove(ds.size() -1). Why not use ds.remove(nums[i]) ?
@@TheMa11nu Since, we only want to remove the value which we added, at last, hence we are using ds. remove(ds. size() - 1). As ds.remove() considers integer value as parameter(index) hence, it will consider that the value you are passing inside remove(nums[i]) is the index, not the value, hence it will remove the incorrect element instead of the last index value & may even give you an error in case value of nums[i] is more than length of ds - 1. Even if you want to remove it by value in that case it will remove first occurrence of that particular value, & in case we have multiple occurrences of that value it will not remove the element from the last index instead it will remove the first occurrence hence your output will be wrong.
sir what about the time complexity of pushing in ans vector...will it not count?
Understood ❤
very helpful
thanks
nice explanantion
I can understand your solution but when it comes to think of logic by myself its problem.when to use loop ,when only recursive calls no loop ,I cant differentiate
Can someone please explain why sometimes we are passing loop's I in recursive call and sometimes we are passing index(from function parameter) to recursive calls. For example in
in this question: recurPermute(index + 1, nums, ans);
in combinations sum 2: findCombinations(i + 1, arr, target - arr[i], ans, ds);
I am finding it hard to get the reason behind this? Please help.
Yes, after a lot of struggle... Finally I figure out why in other cases they are using loop from index to n-1 but in this case they are using 0 to n-1 is because they in permutation at every step you need to move backward as well as in front direction... So in order to take care of backward part they start from 0 .... But in other question we do not need to move backward we need to focus only on the numbers which are coming next.... Not the previous one... So we directly start traversing from index to n-1
@@anantkashyap2087 continuing in simpler terms, in combination/subsets problems we also sort them first, and then to get unique subsets like [1,2], if we did from id+1 else we would have got pairs like [2,1] as well.
Moving to L13 👍 Series is getting difficult with each video
understood!!
Understood !
why use new ArrayList(lst) in base case why cant we just add lst simply
can someone please say how much time should this lesson take? on an average .... as i can't complete it according to the days and questions written in the pdf
C++ code at 16:46
Understood.
Bhiaya I'm not able to code recursively in such questions.
Shouldn't the time complexity be n^n ?
As from the tree at each node we are haveing a loop of n (n branches), and depth of the tree would be n.
understood
Understood🔥
Understood 👍
Thanku Bhaiya
i did the code myself and 😆 did the same code as in the end of video.
I have taken dsa from coding ninjas....but explanation and theory sucks.i was frustated with recursion problems and their deadlines ....but i got your channel somehow now i m ok with recursion
You recommended knowledge gate youtube for it but it doesn't contain all lectures(few of them are private or haven't been uploaded to youtube eg in os series whole topic of process management is missing from youtube ).Should i still continue to it or switch to some other channel ,
Gate smashers
Why are we adding "new ArrayList" to the results ?
I found that without that there is an empty list getting added to the results.
Is there any hint or discretion on when to use 2 recursion call for pick and not pick AND recursion call in for loop. In this playlist there is another problem combination Sum 2 where unique and sorted subsets are derived using for loop with recursion. Please let me know if there is and basic rule that I am missing.