L12. Print all Permutations of a String/Array | Recursion | Approach - 1

Подписаться 664 тыс.

Просмотров 463 тыс.

50% 1

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...
---------------------------------------------------------------------------------------------------------------------------------------------------- I have decided to make a free placement series comprising of video lectures(C++ and Java) on the entire SDE sheet.. ✅(bit.ly/takeUfo...)
✅Entire Series: bit.ly/placemen...
✅Problem Link: leetcode.com/p...
C++/Java Code: takeuforward.o...
Access all the Free Live Classes here: unacademy.cc/da...
Batch for Beginners starting 8th March (Check Course plan) : bit.ly/beginner...
Batch for Intermediates started 4th March: bit.ly/batchascend
Free Test (Exciting prizes for Winners): bit.ly/deadheat...
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_...
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgC...
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/Competiti... (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #leetcode #placements

Опубликовано:

7 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 277

@takeUforward 3 года назад

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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-f2ic2Rsc9pU.html Instagram(For live sessions): instagram.com/striver_79/

@altafmazhar7762 2 года назад

Hi!!

@TheMa11nu 2 года назад

1 question, why we are using ds.remove(ds.size() -1). Why not use ds.remove(nums[i]) ?

@RohitKumar-hh7uu 2 года назад

@@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.

@arpanbanejee5143 3 года назад

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 :)

@sayantaniguha8519 2 года назад

Yaar dono hi aiseee.... tree method se padhayenge na ? Bas iye bta do

@surajsharma2086 2 года назад

@@sayantaniguha8519 yes

@puspendragaming6352 2 года назад

you shoud chack kunal kuswaha recursion.

@tasneemayham974 Год назад

@@puspendragaming6352 He isn't that good. I honestly understood from Striver more than Kunal a thousand times;

@ashishgangwar2744 Год назад

Striver is best

@samlinus836 Год назад

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😁

@samagraagrawal5333 9 месяцев назад

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

@Apsotle_wilson_g 5 месяцев назад

Thanks alot bro........

@mriit3025 5 месяцев назад

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!

@prasannasippa5962 Месяц назад

i code in cpp, but my interviewer asked me to code in java(as i applied for java role) so i missed this step and i got nothing in result, thanks for the explanation:)

@Manish10napstar 2 года назад

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.

@nirnayjain7097 2 года назад

Is string also passed by reference in c++??

@saurabhsaxena1992 2 года назад

@@nirnayjain7097 ya

@codingachinilgtifirbhikrrh9009 2 года назад

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

@Manish10napstar 2 года назад

@@codingachinilgtifirbhikrrh9009 I am generalising here, not talking of any specific programming language.

@harshitsangwan890 2 года назад

@@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.

@SAURABHSINGH-xp8dm 3 года назад

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

@HarshSingh-qq2jf Год назад

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

@Code_With_Goat 2 года назад

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......

@SWATISINGH-im6rd 2 года назад

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.

@vitaminprotein2217 2 года назад

insted of creating int freq[nums.size()]={0} make itin vector as vectormap(nums.size(),0);

@037_sayedramishali7 3 года назад

The reccursion tree is really helpful thank u bhaiya🙏

@mritunjay4ever 3 года назад

Thanks, Raj you don't know how much you help college students like me. This explanation was mind-blowing.

@shreyxnsh.14 3 месяца назад

bro wth, this got accepted on the first try without even looking at your pseudocode (beats 100% as well). Amazing work Striver!!!!

@kirtanprajapati8464 3 года назад

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.

@NikhilKumar-vf9vo 11 месяцев назад

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!

@nkgautam6161 Год назад

afterall..... this is the first ever videos through which i grasp my recursion concept, jiyo striver jiyo

@prikshit8 3 года назад

I hope you are doing extremely well bhaiya ❤️❤️

@nikhilpandeydigital 2 года назад

ur explanation had taken me really forward in understanding this problem as well as recursion, HATS OFF to u and ur work ♥🔥🔥🔥

@scooby8831 Год назад

Your PlayList for recursion is the best .

@stith_pragya 7 месяцев назад

UNDERSTOOD.......Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

@SatyamKumar-bw4vi 2 года назад

Hare Krishna! Thanks Now I can solve the Problem

@nitigya 3 года назад

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.😊

@takeUforward 3 года назад

Yes, we can, but we generally don’t modify the given arr..

@nitigya 3 года назад

@@takeUforward Yeah, got the point! Thank you😁

@rahulsrivastava1040 2 года назад

@@nitigya but it won't work if the array contains negatives as well :\

@nitigya 2 года назад

@@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!

@mohitagarwal1888 2 года назад

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?

@sauvikdas7743 Год назад

I faced the same problem. have you found any solution yet?

@soumojitkoley7154 Месяц назад

using C++ STL vector permute(vector& nums) { vector ans; sort(nums.begin(),nums.end()); do{ ans.push_back(nums); }while(next_permutation(nums.begin(),nums.end())); return ans; }

@akshayvishwakarma188 24 дня назад

thank you sir, well explained!!, and the map technique with just using an array was genius

@codemachine7381 2 года назад

Easiest thing on the planet ... I love recursion

@nityaagrawal1024 2 месяца назад

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.

@neonew339 2 года назад

Great Explanation. There is a good connectivity of the concepts which are taught in the earlier videos of this recursion playlist.

@salmankhader1258 Год назад

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.

@sarthakbhatia7888 2 года назад

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.

@chandrakanthsagar8886 2 года назад

A day to remember me ...when i started ds u r channel is the best

@sandeepparimi5316 Год назад

Great explaination brother! I am really enjoying this series :) This will never get old ❤❤

@jewelchowdhury9752 Год назад

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); }

@arjunc1482 11 месяцев назад

Only man who can go par to par with adithya verma on recursion...truly awsome🤯

@Ayush37262 6 месяцев назад

I have seen both... Striver is much better

@satyamgupta6030 Год назад

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.

@brahamjeet602 2 месяца назад

this channel is a gold mine

@peregrine17 Год назад

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.

@akashjaiswal3120 Год назад

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

@AbhinavSingh-up7bl 11 месяцев назад

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; } }; /////

@narolavarshil6067 2 года назад

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

@dimplevarshney7207 2 года назад

Amazing explanation :) very helpful to understand recursion. I was also thinking in this way but not getting implementation way. thank you so much

@babitabisht060 2 года назад

No doubt video is good but just a suggestion - you should make the viewers see the sudo code first, so that they can get idea of the recursion tree flow. What happening now is that you are explaining the recursion tree at the start but the viewers might not be able to relate it.

@mohdarsalan9090 Год назад

Love the way you solve each and every problem. Kudos to you 💯💯💯💯💯

@nidhinishad7801 Год назад

Python Solution class Solution: def recursion(self,ans,mapp,ds,nums): # base case if len(ds)==len(nums): ans.append(ds.copy()) return for i in range(len(nums)): if not mapp[i]: ds.append(nums[i]) mapp[i]=1 self.recursion(ans,mapp,ds,nums) mapp[i]=0 ds.pop() def permute(self, nums: List[int]) -> List[List[int]]: # recursive solution of permutations using spaces ans = [] #to store all the permutations mapp = [0]*(len(nums)) # to mark the used elements ds = [] # to store the array self.recursion(ans,mapp,ds,nums) return ans

@raunakgupta4-yearb.tech.me278 2 года назад

bestest video I have watched till now for permuataions 🔥🔥

@akshitmangotra5370 2 года назад

Bhai bhai! Maaza aagya.. thanks for such easy explanation.

@himanshugoyal7941 2 года назад

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.

@anantkashyap2087 2 года назад

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

@your_name96 2 года назад

@@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.

@VikashYadavBAI 11 месяцев назад

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.

@sanyamgoyal6417 Год назад

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

@sandeepnallala48 3 года назад

Thank you Raj Brother . elegant explanation with Rec tree.

@ShaliniNegi24 2 года назад

The excel sheet format was super useful.

@yashwanthgowda1517 Месяц назад

Instead of Using a array of freq[] , I think we need use a HashMap because its not necessary that the numbers are given from 0 to n always.

@vikashtiwari7689 10 месяцев назад

I will forward your channel name to those group of students & would invite them to come & comment on this video

@user-cd7lf8nk4c 3 месяца назад

I think the time complexity will be O( n*(1+n+n*(n-1) + n*(n-1)(n-2)+........+n!) ) not O(n*n!)

@kmchary1181 8 месяцев назад

awesome, you are my best teacher

@RAJPATEL-ir7ly Год назад

Striver just used a form of dfs to find the permutations without even mentioning it THAT'S WHY HE IS THE G.O.A.T !!!! THE GOOOAAAT

@GadgetTryoutShorts 3 года назад

thank you very much raj bhai

@philosphize Год назад

Thank You Striver , Was crystal clear video

@sriyansdaga4908 Год назад

In c++ code we do we need vector < vector < int>> permute ( vector & nums) And this vector < vector < int>> ans; Please someone explain

@ritikashishodia675 2 года назад

Ap great ho bhaiya hmm phele next permutation q krne gaye apki sheet ka vha permutation ki need padi to logic bna hi nahi....😔😔😔

@swatirauniyar9062 5 месяцев назад

In Java code, in line number 19, as "ans" is List of List, why is it NOT defined as "List > ans = new ArrayList();"

@anshumaan1024 Год назад

C++ code at 16:46

@priyan8004 4 месяца назад

Thanks Striver !

@swapnilyadav_1138 2 года назад

best explanation of recursion.

@manvibhardwaj725 2 года назад

Thank you for the best explanation

@jayadubey_22 3 года назад

thank you bhaiya 👍🏼

@nyctophilicenigma2838 2 месяца назад

l am confused in the space complexity as we are storing all the arrays in ans. If I say there are n! permutation and each permutation takes O(n) space then space complexity should be O(n*n!). Can someone confirm if I am right or wrong.

@arpantripathi1441 2 года назад

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

@mohammedaffann Год назад

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??

@rishurana9655 2 месяца назад

why are we not incrementing the index like we earlier did in subsequence case?

@yashmunde8005 Год назад

Thanks sir Understood everything

@devinpadron5 7 месяцев назад

Time and space complexity in 13:00

@Purubro Год назад

What an intutive solution 😍

@deepjyotidebnath4122 2 года назад

Love the way u explained 🔥🔥

@yuvrajluhach5665 2 года назад

Moving to L13 👍 Series is getting difficult with each video

@mayankkumar4864 3 года назад

Kindly note that that for line no. 23 in your c++ solution, it shows an error in leetcode complier that Error: variable-sized object may not be initialized, Kindly clarify on this bhaiya pls

@takeUforward 3 года назад

Accepted code h bhai. Ekbr mera code chalao

@shivarajpatil8699 Год назад

same did you find the error?

@Abhishek-tl1ul 2 года назад

Thanks Sir for the explanation

@KalyanNakka Год назад

Why are we adding "new ArrayList" to the results ? I found that without that there is an empty list getting added to the results.

@trishalmandrik1295 3 месяца назад

Good explanation but why do you provide a different code on your website than what you explained in the video?

@aritralahiri8321 3 года назад

Very Nice Explanation !

@pulkitkogta2807 2 дня назад

what will happen in case of repetitions in given array?

@anshumanupadhyaycodes 5 месяцев назад

Got One Doubt, Please reply if you see this, Thanks in Advance. -- This is backtracking way of calculating permutations. I have understood it now. But I am just thinking if this can be solved with BFS? I am seeing that dry run of this algorithm with BFS is analogous but I am not able to differentiate why this is not BFS, or if it is somewhat BFS then How? Please help!!

@pratyushyuvraj4994 2 года назад

why use new ArrayList(lst) in base case why cant we just add lst simply

@vikashtiwari7689 10 месяцев назад

RELEVEL charged 1.5Lakhs for it & poor people are yet clearing EMIs

@amanmotghare7196 Год назад

very good explaination man

@prabhakaran5542 2 месяца назад

Understood ❤

@mohammedraqeeb4392 3 года назад

great video. commenting for more reach

@juniper1059 3 месяца назад

Can anyone please tell me where the link to this google doc of SDE Problems is? I've been trying to find it for a long time

@ajitpalsingh606 6 месяцев назад

coded on my own...Thks striver

@yutaitadori7318 3 года назад

Bhiaya I'm not able to code recursively in such questions.

@Morimove 9 месяцев назад

i did the code myself and 😆 did the same code as in the end of video.

@NazeerBashaShaik 5 месяцев назад

Understood, thank you.

@shaiksoofi3741 7 месяцев назад

Thank you

@UECAshutoshKumar Год назад

Thank you sir

@spardha-yug 2 года назад

Thank you so much.

@vibhoragarwal5425 3 года назад

Great explanation !!!!

@vaibhavsethia70 3 года назад

Understood completely!!

@user-og2mo5bz7b Год назад

how do you handle duplicate elements in the given string?

@shrujaigupta2586 Год назад

You can use sets to avoid duplicate elements, and the better would be simply repeating the above process, and at the end remove the duplicates using maps

@aakashsangwan8756 3 года назад

Another easy way : ) class Solution { public: void permutate(vectornums,vector&ans,int i=0){ if(i==nums.size()-1){ ans.push_back(nums); return; } for(int j=i;j

@takeUforward 3 года назад

Approach 2 i have told.

@aakashsangwan8756 3 года назад

@@takeUforward Sorry ,I just saw that video .