• 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;
}
``````

};

• 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.

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