Backtracking without any improve will always got a TLE. Difference with the "Permutations". So 5ms solution with C++


  • 0
    P
    class Solution {
    public:
    	string getPermutation(int n, int k) {
    		string result = ""; vector<char> data;
    		data.resize(n);
    		for(int i=0; i<n; i++) data[i] = i+1+'0';
    		while( n!=0 ) {
    			int i = Getthefactorial(n, k); int count = n-i-1;
    			for(int l=0; l<count; l++) {
    				result += data[0]; data.erase(data.begin()); n--;
    			}
    			int j = 1; int sum = Calculatethefactorial(i);
    			while((k-j*sum) > 0) j++;
    			result += data[j-1]; data.erase(data.begin()+j-1); n--;
    			k -= (j-1)*Calculatethefactorial(i);
    		}
    		return result;
    		
    	}
        int Getthefactorial(int n, int k) {
        	int result = 1;
        	for(int i=0; i<n; i++) {
        		result *= (i+1);
        		if(result >= k) return i;
        	} 
        }
        int Calculatethefactorial(int n) {
        	int result = 1;
        	for(int i=0; i<n; i++) result *= (i+1);
        	return result;
        }
    };

Log in to reply
 

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