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: ua-cam.com/video/f2ic2Rsc9pU/v-deo.html Instagram(For live sessions): instagram.com/striver_79/
@@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.
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 :)
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😁
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:)
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
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.
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 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
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.
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!
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.
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
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.
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.😊
@@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!
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.
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?
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.
//Method 1 // Bruteforce Approach class Solution { public List find_permutation(String str) { List uniquePermutations = new ArrayList(); findUniquePermutations(str, new StringBuilder(), uniquePermutations, new boolean[str.length()]); Collections.sort(uniquePermutations); return uniquePermutations; } private void findUniquePermutations(String str, StringBuilder permutation, List uniquePermutations, boolean[] visited) { if (permutation.length() == str.length()) { String currentPermutation = permutation.toString(); if (!uniquePermutations.contains(currentPermutation)) { uniquePermutations.add(currentPermutation); } return; } for (int i = 0; i < str.length(); i++) { if (!visited[i]) { visited[i] = true; permutation.append(str.charAt(i)); findUniquePermutations(str, permutation, uniquePermutations, visited); permutation.setLength(permutation.length() - 1); visited[i] = false; } } } } //Improved Approach class Solution { public List find_permutation(String str) { Set uniquePermutations = new TreeSet(); findUniquePermutations(str, new StringBuilder(), uniquePermutations, new boolean[str.length()]); return new ArrayList(uniquePermutations); } private void findUniquePermutations(String str, StringBuilder permutation, Set uniquePermutations, boolean[] visited) { if (permutation.length() == str.length()) { String currentPermutation = permutation.toString(); if (!uniquePermutations.contains(currentPermutation)) { uniquePermutations.add(currentPermutation); } return; } for (int i = 0; i < str.length(); i++) { if (!visited[i]) { visited[i] = true; permutation.append(str.charAt(i)); findUniquePermutations(str, permutation, uniquePermutations, visited); permutation.setLength(permutation.length() - 1); visited[i] = false; } } } } //Better Approach class Solution { public List find_permutation(String str) { char[] arr = str.toCharArray(); Arrays.sort(arr); List uniquePermutations = new ArrayList(); findUniquePermutations(arr, new StringBuilder(), uniquePermutations, new boolean[str.length()]); return uniquePermutations; } private void findUniquePermutations(char[] arr, StringBuilder permutation, List uniquePermutations, boolean[] visited) { if (permutation.length() == arr.length) { uniquePermutations.add(permutation.toString()); return; } for (int i = 0; i < arr.length; i++) { /* * Why are we exactly using !visited[i - 1]? * * 1: To avoid generating duplicate permutations, we need to ensure that we do * not include the same element multiple times at the same level of recursion. * 2: If arr[i] is the same as arr[i - 1] (i.e., a duplicate) and arr[i - 1] has * not been used (!visited[i - 1]), it means we are at the same level of * recursion and should skip arr[i] to avoid generating a duplicate permutation. * If arr[i] is the same as arr[i - 1] (i.e., a duplicate) and arr[i - 1] has * been used (visited[i - 1]==true) it means we are at different level of * recursion and can proceed with a duplicate element as it generates a new * permutation different from those generated at the same level as arr[i - 1]. */ if (i > 0 && arr[i - 1] == arr[i] && !visited[i - 1]) { continue; } if (!visited[i]) { visited[i] = true; permutation.append(arr[i]); findUniquePermutations(arr, permutation, uniquePermutations, visited); permutation.setLength(permutation.length() - 1); visited[i] = false; } } } } //Optimal Approach class Solution { public List find_permutation(String str) { List uniquePermutations = new ArrayList(); findUniquePermutations(str, new StringBuilder(), uniquePermutations, new boolean[str.length()]); Collections.sort(uniquePermutations); return uniquePermutations; } private void findUniquePermutations(String str, StringBuilder permutation, List uniquePermutations, boolean[] visited) { if (permutation.length() == str.length()) { uniquePermutations.add(permutation.toString()); return; } // To keep track of elements used at the current level of recursion Set used = new HashSet(); for (int i = 0; i < str.length(); i++) { if (used.contains(str.charAt(i))) { continue; // Skip duplicates } if (!visited[i]) { used.add(str.charAt(i)); visited[i] = true; permutation.append(str.charAt(i)); findUniquePermutations(str, permutation, uniquePermutations, visited); permutation.setLength(permutation.length() - 1); visited[i] = false; } } } } //Method 2 //Bruteforce Approach class Solution { public List find_permutation(String str) { List uniquePermutations = new ArrayList(); findUniquePermutations(str.toCharArray(), 0, uniquePermutations); Collections.sort(uniquePermutations); return uniquePermutations; } private void findUniquePermutations(char[] arr, int index, List uniquePermutations) { if (index == arr.length) { String currentPermutation = new String(arr); if (!uniquePermutations.contains(currentPermutation)) { uniquePermutations.add(currentPermutation); } return; } for (int i = index; i < arr.length; i++) { swap(arr, index, i); findUniquePermutations(arr, index + 1, uniquePermutations); swap(arr, index, i); } } private void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } //Better Approach class Solution { public List find_permutation(String str) { Set uniquePermutations = new TreeSet(); findUniquePermutations(str.toCharArray(), 0, uniquePermutations); return new ArrayList(uniquePermutations); } private void findUniquePermutations(char[] arr, int index, Set uniquePermutations) { if (index == arr.length) { String currentPermutation = new String(arr); if (!uniquePermutations.contains(currentPermutation)) { uniquePermutations.add(currentPermutation); } return; } for (int i = index; i < arr.length; i++) { swap(arr, index, i); findUniquePermutations(arr, index + 1, uniquePermutations); swap(arr, index, i); } } private void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } //Optimal Approach /* Purpose of sorting : Sorting is used to bring duplicate elements together, so adjacent duplicates can be easily identified and skipped during permutation generation. Why sorting and then skipping won't work here ? Because we are manipulating the input array itself to form the permutation which involves swapping. If you sort the array and then swap elements, the order of elements is modified,the array is no longer in its sorted order, which invalidates the duplicate-checking logic (arr[i] == arr[i - 1]) that assumes adjacent duplicates. */ class Solution { public List find_permutation(String str) { List uniquePermutations = new ArrayList(); findUniquePermutations(str.toCharArray(), 0, uniquePermutations); Collections.sort(uniquePermutations); return uniquePermutations; } private void findUniquePermutations(char[] arr, int index, List uniquePermutations) { if (index == arr.length) { uniquePermutations.add(new String(arr)); return; } // To keep track of elements used at the current level of recursion Set used = new HashSet(); for (int i = index; i < arr.length; i++) { if (used.contains(arr[i])) { continue; // Skip duplicates } used.add(arr[i]); swap(arr, index, i); findUniquePermutations(arr, index + 1, uniquePermutations); swap(arr, index, i); } } private void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
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); }
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.
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.
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
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
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
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??
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.
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: ua-cam.com/video/f2ic2Rsc9pU/v-deo.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.
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:)
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
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
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.
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
bro wth, this got accepted on the first try without even looking at your pseudocode (beats 100% as well). Amazing work Striver!!!!
Thanks, Raj you don't know how much you help college students like me. This explanation was mind-blowing.
The reccursion tree is really helpful thank u bhaiya🙏
Your PlayList for recursion is the best .
Hare Krishna! Thanks Now I can solve the Problem
UNDERSTOOD.......Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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!
A day to remember me ...when i started ds u r channel is the best
I hope you are doing extremely well bhaiya ❤️❤️
ur explanation had taken me really forward in understanding this problem as well as recursion, HATS OFF to u and ur work ♥🔥🔥🔥
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
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;
}
};
/////
thank you sir, well explained!!, and the map technique with just using an array was genius
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.
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
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
Great Explanation. There is a good connectivity of the concepts which are taught in the earlier videos of this recursion playlist.
this channel is a gold mine
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.
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!
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.
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?
awesome, you are my best teacher
Ap great ho bhaiya hmm phele next permutation q krne gaye apki sheet ka vha permutation ki need padi to logic bna hi nahi....😔😔😔
Bhai bhai! Maaza aagya.. thanks for such easy explanation.
Love the way you solve each and every problem.
Kudos to you
💯💯💯💯💯
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.
Great explaination brother! I am really enjoying this series :) This will never get old ❤❤
//Method 1
// Bruteforce Approach
class Solution {
public List find_permutation(String str) {
List uniquePermutations = new ArrayList();
findUniquePermutations(str, new StringBuilder(), uniquePermutations, new boolean[str.length()]);
Collections.sort(uniquePermutations);
return uniquePermutations;
}
private void findUniquePermutations(String str, StringBuilder permutation, List uniquePermutations, boolean[] visited) {
if (permutation.length() == str.length()) {
String currentPermutation = permutation.toString();
if (!uniquePermutations.contains(currentPermutation)) {
uniquePermutations.add(currentPermutation);
}
return;
}
for (int i = 0; i < str.length(); i++) {
if (!visited[i]) {
visited[i] = true;
permutation.append(str.charAt(i));
findUniquePermutations(str, permutation, uniquePermutations, visited);
permutation.setLength(permutation.length() - 1);
visited[i] = false;
}
}
}
}
//Improved Approach
class Solution {
public List find_permutation(String str) {
Set uniquePermutations = new TreeSet();
findUniquePermutations(str, new StringBuilder(), uniquePermutations, new boolean[str.length()]);
return new ArrayList(uniquePermutations);
}
private void findUniquePermutations(String str, StringBuilder permutation, Set uniquePermutations, boolean[] visited) {
if (permutation.length() == str.length()) {
String currentPermutation = permutation.toString();
if (!uniquePermutations.contains(currentPermutation)) {
uniquePermutations.add(currentPermutation);
}
return;
}
for (int i = 0; i < str.length(); i++) {
if (!visited[i]) {
visited[i] = true;
permutation.append(str.charAt(i));
findUniquePermutations(str, permutation, uniquePermutations, visited);
permutation.setLength(permutation.length() - 1);
visited[i] = false;
}
}
}
}
//Better Approach
class Solution {
public List find_permutation(String str) {
char[] arr = str.toCharArray();
Arrays.sort(arr);
List uniquePermutations = new ArrayList();
findUniquePermutations(arr, new StringBuilder(), uniquePermutations, new boolean[str.length()]);
return uniquePermutations;
}
private void findUniquePermutations(char[] arr, StringBuilder permutation, List uniquePermutations, boolean[] visited) {
if (permutation.length() == arr.length) {
uniquePermutations.add(permutation.toString());
return;
}
for (int i = 0; i < arr.length; i++) {
/*
* Why are we exactly using !visited[i - 1]?
*
* 1: To avoid generating duplicate permutations, we need to ensure that we do
* not include the same element multiple times at the same level of recursion.
* 2: If arr[i] is the same as arr[i - 1] (i.e., a duplicate) and arr[i - 1] has
* not been used (!visited[i - 1]), it means we are at the same level of
* recursion and should skip arr[i] to avoid generating a duplicate permutation.
* If arr[i] is the same as arr[i - 1] (i.e., a duplicate) and arr[i - 1] has
* been used (visited[i - 1]==true) it means we are at different level of
* recursion and can proceed with a duplicate element as it generates a new
* permutation different from those generated at the same level as arr[i - 1].
*/
if (i > 0 && arr[i - 1] == arr[i] && !visited[i - 1]) {
continue;
}
if (!visited[i]) {
visited[i] = true;
permutation.append(arr[i]);
findUniquePermutations(arr, permutation, uniquePermutations, visited);
permutation.setLength(permutation.length() - 1);
visited[i] = false;
}
}
}
}
//Optimal Approach
class Solution {
public List find_permutation(String str) {
List uniquePermutations = new ArrayList();
findUniquePermutations(str, new StringBuilder(), uniquePermutations, new boolean[str.length()]);
Collections.sort(uniquePermutations);
return uniquePermutations;
}
private void findUniquePermutations(String str, StringBuilder permutation, List uniquePermutations, boolean[] visited) {
if (permutation.length() == str.length()) {
uniquePermutations.add(permutation.toString());
return;
}
// To keep track of elements used at the current level of recursion
Set used = new HashSet();
for (int i = 0; i < str.length(); i++) {
if (used.contains(str.charAt(i))) {
continue; // Skip duplicates
}
if (!visited[i]) {
used.add(str.charAt(i));
visited[i] = true;
permutation.append(str.charAt(i));
findUniquePermutations(str, permutation, uniquePermutations, visited);
permutation.setLength(permutation.length() - 1);
visited[i] = false;
}
}
}
}
//Method 2
//Bruteforce Approach
class Solution {
public List find_permutation(String str) {
List uniquePermutations = new ArrayList();
findUniquePermutations(str.toCharArray(), 0, uniquePermutations);
Collections.sort(uniquePermutations);
return uniquePermutations;
}
private void findUniquePermutations(char[] arr, int index, List uniquePermutations) {
if (index == arr.length) {
String currentPermutation = new String(arr);
if (!uniquePermutations.contains(currentPermutation)) {
uniquePermutations.add(currentPermutation);
}
return;
}
for (int i = index; i < arr.length; i++) {
swap(arr, index, i);
findUniquePermutations(arr, index + 1, uniquePermutations);
swap(arr, index, i);
}
}
private void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//Better Approach
class Solution {
public List find_permutation(String str) {
Set uniquePermutations = new TreeSet();
findUniquePermutations(str.toCharArray(), 0, uniquePermutations);
return new ArrayList(uniquePermutations);
}
private void findUniquePermutations(char[] arr, int index, Set uniquePermutations) {
if (index == arr.length) {
String currentPermutation = new String(arr);
if (!uniquePermutations.contains(currentPermutation)) {
uniquePermutations.add(currentPermutation);
}
return;
}
for (int i = index; i < arr.length; i++) {
swap(arr, index, i);
findUniquePermutations(arr, index + 1, uniquePermutations);
swap(arr, index, i);
}
}
private void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//Optimal Approach
/*
Purpose of sorting :
Sorting is used to bring duplicate elements together, so adjacent duplicates can be easily identified and skipped during permutation generation.
Why sorting and then skipping won't work here ?
Because we are manipulating the input array itself to form the permutation which involves swapping. If you sort the array and then swap elements, the order of elements is modified,the array is no longer in its sorted order, which invalidates the duplicate-checking logic (arr[i] == arr[i - 1]) that assumes adjacent duplicates.
*/
class Solution {
public List find_permutation(String str) {
List uniquePermutations = new ArrayList();
findUniquePermutations(str.toCharArray(), 0, uniquePermutations);
Collections.sort(uniquePermutations);
return uniquePermutations;
}
private void findUniquePermutations(char[] arr, int index, List uniquePermutations) {
if (index == arr.length) {
uniquePermutations.add(new String(arr));
return;
}
// To keep track of elements used at the current level of recursion
Set used = new HashSet();
for (int i = index; i < arr.length; i++) {
if (used.contains(arr[i])) {
continue; // Skip duplicates
}
used.add(arr[i]);
swap(arr, index, i);
findUniquePermutations(arr, index + 1, uniquePermutations);
swap(arr, index, i);
}
}
private void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
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);
}
Amazing explanation :) very helpful to understand recursion. I was also thinking in this way but not getting implementation way. thank you so much
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
The excel sheet format was super useful.
Thank you Raj Brother . elegant explanation with Rec tree.
Thank You Striver , Was crystal clear video
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.
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.
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
Thank you for the best explanation
Thanks sir Understood everything
best explanation of recursion.
Understood ❤
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
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
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??
Thank you sir
I think the time complexity will be O( n*(1+n+n*(n-1) + n*(n-1)(n-2)+........+n!) ) not O(n*n!)
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;
}
thank you very much raj bhai
understood, thanks for the great video
In c++ code we do we need vector < vector < int>> permute ( vector & nums)
And this
vector < vector < int>> ans;
Please someone explain
very good explaination man
Understood🔥
Thanks Sir for the explanation
I will forward your channel name to those group of students & would invite them to come & comment on this video
Thanks Striver !
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.
Moving to L13 👍 Series is getting difficult with each video
What an intutive solution 😍
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
Approach 2 i have told.
@@takeUforward Sorry ,I just saw that video .
i did the code myself and 😆 did the same code as in the end of 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.
Aa gya smjh
thank you bhaiya 👍🏼
Awesome explanation
Striver OP💯
understood bhaiya
C++ code at 16:46
Love the way u explained 🔥🔥
Thanks a lot , bhaiya
coded on my own...Thks striver
tysm sir
Understood, thank you.
Understood 👍
Thanku Bhaiya
Very Nice Explanation !
Thank you so much.
Thank you
nice explanantion
Good explanation but why do you provide a different code on your website than what you explained in the video?
Time and space complexity in 13:00
excellent man keep it up
great video. commenting for more reach
Nice explanation
very helpful
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.
Great explanation !!!!
Understood completely!!
Beautiful code ! 👌