Simple and Straight Forward Solution in C++ based on Definition of Permutation (18ms)


  • 1
    K
    class Solution {
    public:
        vector<vector<int> > permute(vector<int> &num) {
            vector<vector<int> > res;
            if(num.size()==0) return res;
            vector<int> perm;
            helper(perm,num,res);
            return res;
        }
        void helper(vector<int> &perm, vector<int> &num, vector<vector<int> > &res){
            if(num.size()==0){  
                //As the element chosen from num to put in the perm is erased each time, 
                //when num is empty, perm is exactly the final permutation.
                res.push_back(perm);
                return;
            }
            for(int i=0;i<num.size();i++){
                int digit=num[i];   //Store the digit that will be erased for next step in order to put it back when return.
                perm.push_back(digit);
                num.erase(num.begin()+i);   //Erase the digit that was chosen to put in perm
                helper(perm,num,res);   
                perm.pop_back();    //Using reference as parameters will be time efficient, but we have to pop out the last one.
                num.insert(num.begin()+i,digit); // Insert the erased element back.
            }
        }
    };

  • 0
    D
    void genPermutation(vector<vector<int> > & r, vector<int> & nums, int start, int end) {
        if( start > end ) {
            r.push_back(nums);
        } else {
            for( int i = start; i <= end; i++) {
                swap(nums[start], nums[i]);
                genPermutation(r, nums, start + 1, end);
                swap(nums[start],nums[i]);
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > r;
        genPermutation(r, nums, 0, nums.size()-1);
        return r;
    }
    

    My method is alike yours but didn't need to actually erase/insert elements in the original vectors. Also 18ms runtime


Log in to reply
 

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