The algorithm is as below:

- Add num to res_0.
- For each vector v in res_0 (now it only has num), swap v[0] with every element after 0, add the new vector to res_0, and get res_1. Note that res_1 has 1 + (n - 1) permutations.
- Repeat 2 for res_i (i = 0, 1, ..., n - 2): for each vector v in res_i, swap v[i] with every element after i, add the new vector to res_i, and get res_(i+1). Then res_(n - 1) will be the solution.

The correctness of the above algorithm can be proven by induction. Assume that res_i contains unique permutations. Note that

- The new permutations which are added to res_(i + 1) are different from the old ones in res_i, and the new permutations which are generated from the same permutation in res_i are different from each other.
- The new permutations which are generated from different permutation in res_i are different because they have different "prefixes".

Besides, cntOfVectors(res_0) = 1

==> cntOfVectors(res_1) = 1 + 1*(n - 1) = n

==> ...

==> cntOfVectors(res_(n - 1)) = n*(n - 1)*... 3 + n(n - 1)*...

*3*1 = n!

```
class Solution {
public:
vector<vector<int>> permute(vector<int> &num)
{
vector<vector<int>> res({num});
vector<int> tmpV;
int n = num.size();
int tmp = 0;
for (int i = 0; i < n - 1; i++)
{
int m = res.size();
for (int k = 0; k < m; k++)
{
for (int j = i + 1; j < n; j++)
{
tmpV = res[k];
tmp = tmpV[i];
tmpV[i] = tmpV[j];
tmpV[j] = tmp;
res.push_back(tmpV);
}
}
}
return res;
}
};
```