The DFS_based Backtracking is obvious for this problem.

However how to build neighbor of a vertex makes me struggle for a while.

My first solution is like below:

Running Time: beats 42.82%

```
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> solutions;
vector<int> solution;
recursion(0, nums, solution, solutions);
return solutions;
}
void recursion(int pos, vector<int>& nums, vector<int>& solution, vector<vector<int>>& solutions) {
// exit condition
if (pos == nums.size()) {
solutions.push_back(solution);
return;
}
//recursive calling
for (int i = 0; i <= solution.size(); i++) {
solution.insert(solution.begin() + i, nums[pos]);
recursion(pos + 1, nums, solution, solutions);
solution.erase(solution.begin() + i);
}
}
```

In each recursion I insert nums[pos] into different index of partial solution. I have to say this approach generates permutations in a weird order, it is [3,2,1], [2,3,1], [2, 1 ,3]... Moreover as we all know it is bad idea to repeatedly do the random insert and erase to vector. So the running time is so slow.

The second approach would be more natural

Running time : beats 90.96%

```
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> solutions;
vector<int> solution;
recursion(nums, solution, solutions);
return solutions;
}
void recursion(vector<int>& nums, vector<int>& solution, vector<vector<int>>& solutions) {
// exit condition
if (solution.size() == nums.size()) {
solutions.push_back(solution);
return;
}
//recursive calling
for (int i = 0; i < nums.size(); i++) {
if (find(solution.begin(), solution.end(), nums[i]) != solution.end())
continue;
solution.push_back(nums[i]);
recursion(nums, solution, solutions);
solution.pop_back();
}
}
```

We can just add a if condition to see whether nums[i] is already in our vertex. If so, we can't use it to extend our vertext or build the neighbor. In this way, we just apply query operation to vector, which is much faster than dynamic operation.