# My non-recursive C++ solution without two vector<vector<int>>

• The algorithm is as below:

2. 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.
3. 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)...31 = 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;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.