Three weeks ago this solution got accepted now its giving TLE.


  • 1
    G
    class Solution {
    public:
        void permutation(set<vector<int> > &all,  vector<int> num, int s, int e)
        {
            if(s==(e+1))
            {
                all.insert(num);
                return;
            }
            for(int i=s; i<=e; i++)
            {
                //swap num[i] and num[s]
                int tmp = num[i];
                num[i] = num[s];
                num[s] = tmp;
                
                permutation (all, num, s+1, e);
                
                //swap num[i] and num[s]
                tmp = num[i];
                num[i] = num[s];
                num[s] = tmp;
            }
        }
        vector<vector<int> > permuteUnique(vector<int> &num) {
           int n = num.size();
           vector<vector<int> > ans;
           if(!n)
             return ans;
             
           set<vector<int> > all;
           permutation(all, num, 0, n-1);
           
           set<vector<int> >::iterator it;
           for(it=all.begin(); it != all.end(); it++)
           {
               ans.push_back(*it);
           }
        }
    };

  • 1

    Yes, this solution should TLE because you are using set to avoid duplicates, and this is not optimal.

    The reason it did not TLE three weeks ago was due to a mistake on the judger itself which is fixed now.


  • 0
    S

    could you show us the correct code,thanks


Log in to reply
 

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