Copy Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Copy Input: nums = [0,1]
Output: [[0,1],[1,0]]
Copy Input: nums = [1]
Output: [[1]]
Copy Take an element at every position
Approach 1 :
MAintain a map for marking which element is taken and push the elements accordingly
Approach 2: Eliminate the extra map space
Basically, Swap elemnts such that all elemets gets a chance at all position
Once swapped, swap other elements of remaining array
Copy class Solution {
public :
vector < vector < int >> find_ans ( vector < vector < int >> & ans , vector < int > & nums ,
vector < int > & temp , unordered_map < int , bool > & mp){
if ( temp . size () == nums . size ()){
ans . push_back (temp);
return ans;
}
/*
Pushing and marking the element in the map
When we return unmark the array and proceed
*/
for ( int i = 0 ; i < nums . size (); i ++ ){
if ( mp . find (i) == mp . end ()){
temp . push_back ( nums [i]);
mp [i] = true ;
find_ans (ans , nums , temp , mp);
temp . pop_back ();
mp . erase (i);
}
}
return ans;
}
vector < vector < int >> permute ( vector < int > & nums) {
vector < vector <int>> ans;
unordered_map <int , bool> mp;
vector <int> temp;
return find_ans (ans , nums , temp , mp);
}
};
Copy class Solution {
public :
vector < vector < int >> find_ans ( vector < vector < int >> & ans , vector < int > & nums , int index){
if (index == nums . size ()){
ans . push_back (nums);
return ans;
}
for ( int i = index; i < nums . size (); i ++ ){
swap ( nums [index] , nums [i]);
find_ans (ans , nums , index + 1 );
swap ( nums [index] , nums [i]);
}
return ans;
}
vector < vector < int >> permute ( vector < int > & nums) {
vector < vector <int>> ans;
return find_ans (ans , nums , 0 );
}
};