LeetCode 060 Permutation Sequence

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        # let permutations with first identical num be a block
        # target in (k - 1) / (n - 1)! block
        remain = range(1, n + 1)
        if k <= 1:
            return ''.join(str(t) for t in remain)
        total = 1
        for num in remain[:-1]:
            total *= num
        res = self.do_getPermutation(remain, total, n - 1, k - 1)
        return ''.join(str(t) for t in res)


    def do_getPermutation(self, remain, curr, n, k):
        if n == 0 or k <= 0 or curr == 0:
            return remain
        # which block
        step = k / curr
        # remain k value
        k %= curr
        curr /= n
        res = [remain[step]] + self.do_getPermutation(remain[:step] + remain[step + 1:], curr, n - 1, k)
        return res

if __name__ == '__main__':
    s = Solution()
    print s.getPermutation(3, 2)
    # print s.getPermutation(2, 2)