Simple recursive C++. slow because of vector copies


  • 0
    B

    I'd imagine there's some low-hanging optimizations here to reduce all the copying.

    class Solution {
    public:
        vector<vector<int> > permute(vector<int> &num) {
            vector<int> foo;
            buildPermutations(foo, num, num.size());
            return permutations;
        }
    private:
       void buildPermutations(const vector<int>& perm, const vector<int>& remaining, const int sizeLimit) {
           if(perm.size() == sizeLimit) {
               permutations.push_back(perm);
               return;
           }
        
           for(int i = 0; i < remaining.size(); i++) {
               vector<int> newRem = remaining;
               vector<int> newPerm = perm;
            
               newRem.erase(newRem.begin() + i);
               newPerm.push_back(remaining[i]);
            
               buildPermutations(newPerm, newRem, sizeLimit);
           }
        }
    
        vector<vector<int>> permutations;
    };

Log in to reply
 

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