L12. Print all Permutations of a String/Array | Recursion | Approach - 1
ฝัง
- เผยแพร่เมื่อ 22 ส.ค. 2024
- 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
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!
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:)
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.
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
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
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......
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.
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: th-cam.com/video/f2ic2Rsc9pU/w-d-xo.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.
The reccursion tree is really helpful thank u bhaiya🙏
insted of creating int freq[nums.size()]={0} make itin vector as vectormap(nums.size(),0);
thank you sir, well explained!!, and the map technique with just using an array was genius
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;
}
Thanks, Raj you don't know how much you help college students like me. This explanation was mind-blowing.
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!
I hope you are doing extremely well bhaiya ❤️❤️
bro wth, this got accepted on the first try without even looking at your pseudocode (beats 100% as well). Amazing work Striver!!!!
afterall..... this is the first ever videos through which i grasp my recursion concept, jiyo striver jiyo
Your PlayList for recursion is the best .
ur explanation had taken me really forward in understanding this problem as well as recursion, HATS OFF to u and ur work ♥🔥🔥🔥
UNDERSTOOD.......Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Hare Krishna! Thanks Now I can solve the Problem
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!
this channel is a gold mine
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?
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);
}
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.
A day to remember me ...when i started ds u r channel is the best
Easiest thing on the planet ...
I love recursion
Only man who can go par to par with adithya verma on recursion...truly awsome🤯
I have seen both... Striver is much better
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
Great Explanation. There is a good connectivity of the concepts which are taught in the earlier videos of this recursion playlist.
Great explaination brother! I am really enjoying this series :) This will never get old ❤❤
I will forward your channel name to those group of students & would invite them to come & comment on this video
C++ code at 16:46
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.
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
Bhai bhai! Maaza aagya.. thanks for such easy explanation.
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.
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.
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;
}
};
/////
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.
Amazing explanation :) very helpful to understand recursion. I was also thinking in this way but not getting implementation way. thank you so much
Love the way you solve each and every problem.
Kudos to you
💯💯💯💯💯
awesome, you are my best teacher
bestest video I have watched till now for permuataions 🔥🔥
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
Time and space complexity in 13:00
I think the time complexity will be O( n*(1+n+n*(n-1) + n*(n-1)(n-2)+........+n!) ) not O(n*n!)
Ap great ho bhaiya hmm phele next permutation q krne gaye apki sheet ka vha permutation ki need padi to logic bna hi nahi....😔😔😔
The excel sheet format was super useful.
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
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
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.
thank you very much raj bhai
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.
Thanks Striver !
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.
Thank you Raj Brother . elegant explanation with Rec tree.
Thank You Striver , Was crystal clear video
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.
RELEVEL charged 1.5Lakhs for it & poor people are yet clearing EMIs
thank you bhaiya 👍🏼
Thank you for the best explanation
Thanks sir Understood everything
"Understood!!"
best explanation of recursion.
very good explaination man
Moving to L13 👍 Series is getting difficult with each video
understood
Understood ❤
Time complexity at: 13:00
Thank you sir
Thank you
Understood🔥
Thanks Sir for the explanation
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
Love the way u explained 🔥🔥
coded on my own...Thks striver
Very Nice Explanation !
i did the code myself and 😆 did the same code as in the end of video.
How to get the approach of these difficult questions if we haven't seen them before?
simple , First saw them
@@vibhoragarwal5425 heheeheh
Nobody can do that. It's all about solving similar question. Then only you can solve question on that topic. Solve atleast 15 question on each topics and revise them.
@@vibhoragarwal5425 see *
Understood, thank you.
What an intutive solution 😍
Striver OP💯
great video. commenting for more reach
Aa gya smjh
Awesome explanation
Understood
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
Accepted code h bhai. Ekbr mera code chalao
same did you find the error?
Thank you so much.
tysm sir
Good explanation but why do you provide a different code on your website than what you explained in the video?
Bhiaya I'm not able to code recursively in such questions.
nice explanantion
Thanks a lot , bhaiya
In c++ code we do we need vector < vector < int>> permute ( vector & nums)
And this
vector < vector < int>> ans;
Please someone explain
excellent man keep it up
Nice explanation
Great explanation !!!!
understood.