```
class Solution(object):
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
factorials = [1]*n
for i in range(1, n): factorials[i] = factorials[i-1]*(i+1)
candidates = list(str(x) for x in range(1, n+1))
ans = ['']
def collect(remain, kCandidate):
if kCandidate <= 0: return
nGroup = factorials[kCandidate-2]
first_index = (remain-1)/nGroup
ans[0] += candidates.pop(first_index)
collect(remain%nGroup, kCandidate-1)
collect(k, n)
return ans[0]
```