Output Limit Exceeded


  • 0
    L

    Hi, all. Got a little problem here. The code I have can't be accepted because it says output limit exceeded. I am quite confused because I can't seem to figure out how my code could produce too much outputs.

    The way my code works is as follows. It continuously takes out element from the original array one at a time until the array with only one element left. And then the code works backwards to get the permutations when adding the elements back one by one. To determine the duplicates, it uses a set to keep track of all the inserted vectors. The string version of the vector is stored in the set to determine the duplicates. Sorry I know I cheated here but I just want to get the problem solved first. I do have another version of the code that doesn't uses the set but that still gives the same problem. ;(.
    Hope someone could help me figure out the problem of my code. Thanks!

    class Solution {
    public:
        vector<vector<int> > permuteUnique(vector<int> &num) {
            vector<vector<int>> ret;
            if (num.size()==1){
                ret.push_back(num);
                return ret;
            } 
            
            int back = num.back();
            num.pop_back();
            
            vector<vector<int>> res = permuteUnique(num);
            for(int i =0; i <res.size(); ++i)
            {
                vector<int> localVector = res[i];
                
                helper(back, localVector, &ret);
            }
            return ret;
        }
        
        void helper(int val, vector<int> v, vector<vector<int>>* ret)
        {
            vector<int>::iterator it;
            set<string> s;
            for (int i =0; i <=v.size(); ++i)
            {
                vector<int> temp = v;
                it = temp.begin();
                it += i;
                temp.insert(it, val);
                
                if (!contains(s,temp))
                {
                    //Only add the vector if it is not a duplicate.
                    ret->push_back(temp);
                }
            }
            
        }
        
        bool contains(set<string>& s, vector<int> v)
        {
            string str = "";
            for(int i = 0; i < v.size(); ++i)
            {
                str += to_string(v[i]);
            }
            if (s.find(str)!=s.end())
            {
                return true;
            }
            else
            {
                s.insert(str);
                return false;
            }
        }
    };

  • 0
    L

    I copied the same code into the Permutation One, and it actually accepted. Could this be the testcase's problem?

    Can someone who solved the problem before and re-submitted the code to see it still can be accepted?

    P.S. I think for some weird reason, the set is not doing what I expected to do... The duplicate items still got inserted...


  • 0
    G

    I also get Output Limit Exceeded and I don't seem to understand what it means.

    I don't think it is a problem with Sets. I have not used Sets in my code. I still have the same problem as you. Also the following code when copy pasted in the Permutation 1 gets accepted.

    #include<algorithm>
    
    class Solution {
    public:
        vector<vector<int> > ans;
        
        void fn(vector<int> &num, int pos)
        {
            if(pos==num.size()-1)
            {
                ans.push_back(num);
                return;
            }
            else
            {
                int a,b,i;
                fn(num,pos+1);
                a = num[pos];
                for(i=pos+1;i<num.size();i++)
                {
                    if(a!=num[i])
                    {
                    b = num[i];
                    num[pos] = b; 
                    num[i] = a;
                    fn(num,pos+1);
                    num[pos] = a;
                    num[i] = b;
                    }
                }
            }
        }
        
        vector<vector<int> > permuteUnique(vector<int> &num) {
            sort(num.begin(),num.end());
            fn(num,0);
            return ans;
        }
    };

  • 1
    L

    It turns out it is my code's problem. The set I am using should not be put inside the helper() function. As the result of that, the set can't properly distinguish the unique permutation. Instead, it should be placed before the "for" loop of the permuteUnique() function and the solution is accepted.

    For gpraveenkumar, I think the test cases are correct. Your code probably failed to take out the duplicates. Try to run through your code with a sample test i.e. [1,2,1] and see what you got.


  • 0
    S

    Could you please format your code correctly? Your post is more like a question. Hope you can re-post it as a question, people might not notice your problem here. Thanks.


  • 0
    G

    My code works fine on a local machine. Did your program get accepted ?


  • 0
    G

    I had formatted my code, sorry don't know how it got messed up. I did not post is as a new question, because it was consistent with the question posted by the OP.


  • 0
    G

    My Program works now. You were sort of correct. Since I wasn't using sets, my program had repeats for cases where more than one number occurs more than once for eg. [1,2,1,2]


  • 0
    K

    I think that you should not use the set to remove duplicates. There is a way to remove duplicates efficiently without using set. I got accepted with that way.


  • 0
    R

    The line if (a!=num[i]) only prevents a from appear twice at pos. What if for some i,j such that a != num[i] == num[j]?


Log in to reply
 

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