Why not just implement next_permutation, then call it factorial(nums.size()) times?


  • 0
    K

    Straightforward C++ code runs in 12ms: the same as the fastest available.

    class Solution {
        template<class I>
        void my_next_permutation(I b, I e) {
            if (e - b < 2)
                return;
    
            auto miss = e - 2;
            while(miss > b) {
                if (*miss < *(miss+1)) 
                    break;
                --miss;
            }
            if (miss == b && *miss >= *(miss+1)) { // 'highest'
                reverse(b, e);
                return;
            }
            I pos = e-1;
            while(*pos <= *miss) 
                --pos;
            swap(*pos, *miss);
            reverse(miss+1, e);
            
            
        }
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            size_t c = 1;
            for (int i = 1; i <= nums.size(); ++i)
                c*=i;
            cout << c << endl;
            vector<vector<int>> out;
            out.reserve(c);
            
            out.push_back(nums);
            while (out.size() < c) {
                out.push_back(out.back());
                my_next_permutation(out.back().begin(), out.back().end());
            }
            return out;
        }
    };

Log in to reply
 

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