Time limit exceeded using conventional backtracking approach....please help


  • 0
    T

    class Solution {

    int perm_count;
    string kth_perm;
    bool found;
    void permute(string s,int k,int start,int end)
    {
        if(start == end)
        {
            perm_count++;
            if(perm_count == k)
            {
                found = true;
                kth_perm.append(s);
                return ;
            }
        }
        if(found)
            return;
            
        for(int index = start;index <= end;index++)
        {
            std::swap(s[index],s[start]);
            permute(s,k,start + 1,end);
            std::swap(s[index],s[start]);
        }
    }
    
    int fact(int n)
    {
        if(n == 1||n == 0)
            return 1;
        else
            return n * fact(n - 1);
    }
    

    public:

    string getPermutation(int n, int k) {
        string s;
        if(k == 0 || k > fact(n))
            return s;
            
        for(int i = 1;i <= n;i++)
            s.append(to_string(i));
        perm_count = 0;
        found = false;
        permute(s,k,0,n - 1);
        return kth_perm;
    }
    

    };


  • 0
    T

    Hi,
    Your algorithm would not work for this problem. 1, the way you generate permutation is not correct. I checked your code and it's not correct even for small n and k. 2, even if you get the algorithm correct, it would be very slow for large number of k. for n = 9, k = 30000 you would have to call permute 30000 times! it would definitely exceed time limit. You have to try a different way to solve the problem.


Log in to reply
 

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