class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > res;
if(num.size()==0) return res;
vector<int> perm;
helper(perm,num,res);
return res;
}
void helper(vector<int> &perm, vector<int> &num, vector<vector<int> > &res){
if(num.size()==0){
//As the element chosen from num to put in the perm is erased each time,
//when num is empty, perm is exactly the final permutation.
res.push_back(perm);
return;
}
for(int i=0;i<num.size();i++){
int digit=num[i]; //Store the digit that will be erased for next step in order to put it back when return.
perm.push_back(digit);
num.erase(num.begin()+i); //Erase the digit that was chosen to put in perm
helper(perm,num,res);
perm.pop_back(); //Using reference as parameters will be time efficient, but we have to pop out the last one.
num.insert(num.begin()+i,digit); // Insert the erased element back.
}
}
};
Simple and Straight Forward Solution in C++ based on Definition of Permutation (18ms)


void genPermutation(vector<vector<int> > & r, vector<int> & nums, int start, int end) { if( start > end ) { r.push_back(nums); } else { for( int i = start; i <= end; i++) { swap(nums[start], nums[i]); genPermutation(r, nums, start + 1, end); swap(nums[start],nums[i]); } } } vector<vector<int>> permute(vector<int>& nums) { vector<vector<int> > r; genPermutation(r, nums, 0, nums.size()1); return r; }
My method is alike yours but didn't need to actually erase/insert elements in the original vectors. Also 18ms runtime