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


  • 1
    Z

    The algorithm is as below:

    1. Add num to res_0.
    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;
        }
    };

Log in to reply
 

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