Permutations II | Two Approaches | Detailed | Recursion Concepts And Questions

This is the 16th video of our playlist "Recursion Concepts And Questions". Find the Details below :

Video Name : Permutations II | Two Approaches | Recursion Concepts And Questions
Video # : 16

🔍 Unraveling Recursion: A Journey into the Depths of Code

🎥 Welcome to the 16th Video of my Recursion Playlist! 🚀 In this enlightening video, we will solve another very famous recursion/backtracking problem "Permutations II". We will start with a Simple story as well as Tree Diagram for understanding the problem and then we will be Converting Story to code and writing the recursive code for the problem and also I will also be explaining the Time and Space Complexity of the code 🌐. We will be solving it using the same approach as the Permutations I with slight enhancement to handle duplicate cases.

🔍 What's Inside?

🔗 Simple story understanding with Tree Diagram

🔗 Converting Story to code and writing the recursive code for Permutations II problem

🔗 Explanation of Time and Space Complexity of the code

👩‍💻 Who Should Watch?

This playlist is for everyone but best suited for Freshers who are new to Recursion.

🚀 Embark on the Recursive Adventure Now!

Approach Summary :
Approach-1 (Using same concept as Permutation-I but keeping count to avoid duplicates):

This approach employs backtracking to generate unique permutations of a given set of numbers. The algorithm maintains a count of the occurrences of each number using an unordered map. It iterates through the map, choosing each number and recursively exploring permutations while updating counts. This ensures duplicates are avoided by keeping track of the count of each number. The time complexity is O(N * N!), where N is the number of elements in the input array, and the space complexity is O(N).

Approach-2 (Using swap technique but avoiding duplicates by using set):

This approach utilizes the swap technique for generating permutations while preventing duplicates using a set to track unique elements. The algorithm recursively swaps elements at different positions and skips duplicates by checking against a set. This ensures that each permutation is unique. The time complexity is O(N * N!) in the worst case, where N is the number of elements in the input array, and the space complexity is O(N). The set is used to store unique elements during the recursive process.

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

00:00 - Introduction
00:10 - Motivation (Bhashan)
01:45 - Problem Explanation
03:03 - Recall Permutation-I Approach-1
08:00 - Why it fails for Permutations-II
09:49 - Correcting Approach-1 for Permutations-II
15:37 - Coding Approach-1
19:20 - Time & Space Complexity
21:47 - Recall Permutation-I Approach-2
26:26 - Why it fails for Permutations-II
29:52 - Correcting Approach-2 for Permutations-II
35:35 - Coding Approach-2
39:34 - Time & Space Complexity

#codestorywithMIK
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear #RecursionExplained #CodingJourney #Programming101 #TechTalks #AlgorithmMastery #Recursion #Programming #Algorithm #Code #ComputerScience #SoftwareDevelopment #CodingTips #RecursiveFunctions #TechExplained #ProgrammingConcepts #CodeTutorial #LearnToCode #TechEducation #DeveloperCommunity #RecursiveThinking #ProgrammingLogic #ProblemSolving #AlgorithmDesign #CSEducation

[JagannathDebGunin]

Thanks dada for keeping my request
Thanks a lot 🙏🙏

[riyaverma]

hey! when i first saw your video i thought why would any one recquire motivation, its just waste of time but now i understand why ?... It really helps thank you !

[wearevacationuncoverers]

0:10 we are with you sir. just keep teaching like this. Machaenge ekdm sir. interviews fodenge.

[DevOpskagyaan]

Thank you so much. I am a big fan of your teaching style

[Sarthak-bktd]

just a general question i understood this whole code and first part also perfectly point is i didnt get like what does that auto function do like i never used it as such at how is it working at this 16:48

[someshnayakrollno.-sec-b]

AUXILLIARY SPACE -O(n^2) nhi hoga kyuki worst case mae har recursion call ke liye ek set bana rhe hai??

[rode_atharva]

class Solution {
public:
void backtrack(int &n, vector<vector<int>>& ans, vector<int>& temp, vector<int>& nums, vector<bool>& visited){
if(temp.size() == n){
if(find(ans.begin(), ans.end(), temp) == ans.end()){
ans.push_back(temp);
}

return;
}
for(int i{0}; i<n; i++){
if(visited[i]){
continue;
}
temp.push_back(nums[i]);
visited[i] = true;
backtrack(n, ans, temp, nums, visited);
temp.pop_back();
visited[i] = false;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ans;
vector<int> temp;
vector<bool> visited(n, false);
backtrack(n, ans, temp, nums, visited);
return ans;
}
};

[warlordyt]

mik why we have to take local unordered set? why we dont erase the inserted element while backtracking

[yogitachauhan]

Hi Mike, I saw your few videos and they are amazing and well explained, I am looking for topic wise playlist, like which topic I should go first as a beginner in you channel, can you please share the list of topics I should start first, and can I find those in your channel?
Thanks :)

[rode_atharva]

class Solution{
public:
void backtrack(int idx, string s, string str, vector<string>& ans){
if(str.length() == s.length()){
return;
}
for(int i{idx+1}; i<s.size(); i++){
str += s[i];
ans.push_back(str);
backtrack(i, s, str, ans);
str.pop_back();
}
}
vector<string> AllPossibleStrings(string s){
vector<string> ans;
backtrack(-1, s, "", ans);
sort(ans.begin(), ans.end());
return ans;
}
by myself

[vaibhavgala]

Sir why cant we do this without hashset I tried to so it in java using but fails last test case 3 hours se kar rha 😢 but anyways good video

[AkOp-bfvm]

WHY THIS APPROACH IS NOT WORKING
#include<bits/stdc++.h>
using namespace std;

void solve(int ind, vector<int> &arr, vector<vector<int>> &result){
if(ind>=arr.size()) result.push_back(arr);
for(int i=ind;i<arr.size();i++){
if(i!=ind && (arr[i]==arr[i-1] ||arr[i]==arr[ind])) continue;
// if(i!=ind && arr[i]==arr[ind]) continue;

swap(arr[i], arr[ind]);
solve(ind+1, arr, result);
swap(arr[i], arr[ind]);

}
}

int main(){
vector<int> arr={1, 2, 1, 2};
vector<vector<int>> result;
sort(arr.begin(), arr.end());
solve(0, arr, result);
for ( auto &row : result) {
for ( auto &element : row) {
cout << element << " ";
}
cout << endl;
}
return 0;
}