Leetcode 60. Permutation Sequence

https://leetcode.com/problems/permutation-sequence/

This problem is a little tricky because it requires some math thinking.

Solution:

# T:O(n^2) S:O(n)
class Solution:
    # @param {integer} n
    # @param {integer} k
    # @return {string}
    def getPermutation(self, n, k):
        res, k, fac = '', k-1, 1
        for i in range(1, n): fac *= i
        num = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        for i in reversed(range(n)):
            curr = num[k/fac]
            res += str(curr)
            num.remove(curr)
            if i !=0:
                k %= fac
                fac /= i
        return res

Run Time: 44 ms