Could you help me figure out where is the bug for the problem "Permutations"?


  • 1
    X

    Hi All

    I am trying to solve the problem is "Permutations".

    However, I found

    Status: Runtime Error
    Last executed input: [0,1]

    Could you help me figure out where is the bug?

    I could not find it.

    It is very likely in the line

    for(int j=0; j<n; j++){//???

    Thanks in advance

    class Solution {
    public:
    vector<vector<int> > permute(vector<int> &num) {

        vector<vector<int>> res;
        
        int n=num.size();
        
        if(n==0) return res;
        
        permute(res,num,n);
        
        return res;
    }
    
    void permute(vector<vector<int>> &res, vector<int> &num, int n){
        if(n==1){
            res.push_back(vector<int>(num[0]));
            return;
        }
        
        permute(res, num, n-1);
        
        int resn = res.size();
        vector<int> work;
        
        for(int i=0; i<resn; i++){
            for(int j=0; j<n; j++){//???
                work = res[i];
                work.insert(work.begin()+j,num[n-1]);
                res.push_back(work);
                work.clear();
            }
        }
        
        res.erase(res.begin(),res.begin()+resn);
        
        return;
        
    }
    

    };


  • 0

    Could you please format your code by selecting your code and press the {} button? Please read the FAQ to understand the guidelines of asking a question.


  • 0
    T

    @xiaohl1986: It's a good practice to explain one's algo (be it, comments in code).


  • 0
    F
    vector &num => vector<int> &num
    
    vector<vector<int>> => vector<vector<int> > &num
    
    res.push_back(vector<int>(num[0])); => res.push_back(vector<int>(1, num[0])); //the cause of your runtime error
    
    vector<int> work; //may cause stack-overflow (the vector capacity is not guaranteed to change due to calling clear() function.)
    

    try to avoid "insert" on vector


  • 0
    X

    Thanks.
    Just learned that insert is an very expensive operation if it is not at the "end".


Log in to reply
 

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