Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order (C++). This is Leetcode 46 (Permutations).

This is a solution that I have trouble understanding, I wrote comments with questions.

class Solution {

public:

vector> permute(vector& nums) {

//base case, why is it necessary?

if(nums.size() <= 1){

return {nums};

}

vector> result;

for(int i = 0; i < nums.size(); i++){

vector v(nums.begin(),nums.end());

v.erase(v.begin() + i);

auto res = permute(v); //Why does permute(v) work here if our function is inside permute? Since permute is a vector of a vector does that mean permute(v) will make res a vector of a vector only containing the current v value, (in which v is a value of nums where 1 element is removed)?

for(int j = 0; j < res.size(); j++){ //wouldn't res.size() always be of size 1?

vector vfirst = res[j]; //don't understand

vfirst.insert(vfirst.begin(),nums[i]); //vector_name.insert (position, val) // don't understand

result.push_back(vfirst); //places into last element of vector //don't understand

}

}

return result;

}

};

Also, what is the time complexity of this algorithm? Is it O(n!)?