<p>The set <code>[1, 2, 3, ...,&nbsp;n]</code> contains a total of <code>n!</code> unique permutations.</p>

<p>By listing and labeling all of the permutations in order, we get the following sequence for <code>n = 3</code>:</p>

<ol>
	<li><code>&quot;123&quot;</code></li>
	<li><code>&quot;132&quot;</code></li>
	<li><code>&quot;213&quot;</code></li>
	<li><code>&quot;231&quot;</code></li>
	<li><code>&quot;312&quot;</code></li>
	<li><code>&quot;321&quot;</code></li>
</ol>

<p>Given <code>n</code> and <code>k</code>, return the <code>k<sup>th</sup></code> permutation sequence.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> n = 3, k = 3
<strong>Output:</strong> "213"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> n = 4, k = 9
<strong>Output:</strong> "2314"
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> n = 3, k = 1
<strong>Output:</strong> "123"
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 9</code></li>
	<li><code>1 &lt;= k &lt;= n!</code></li>
</ul>

import numpy as np
class Solution:
    # def getPermutation(self, n: int, k: int) -> str:
    #     fact = [1 for _ in range(n+1)]
    #     for i in range(1,n+1):
    #         fact[i] = fact[i-1]*(i)
    #     full = -1 # full = i! for some i
    #     for time in range(1,n+1):
    #         if fact[time] > k:
    #             full = time-1
    #             break
       
    #     nums = [i+1 for i in range(n)]
    #     for _ in range(k-1):
    #         nums = self.nextSequence(nums)
    #         # print(nums)
    #     return "".join(str(x) for x in nums)

    # def nextSequence(self,nums):
    #     n = len(nums)
    #     # scan from left and where there is dip in value swap 
    #     prev = nums[n-1]
    #     break_i = -1
    #     for i in range(n-2,-1,-1):
    #         if nums[i] < prev: # it is the breakpoint, find next large number
    #             break_i = i
    #             break
    #         else:
    #             prev = nums[i]
    #     # print(f"Break i is {break_i} and number is {nums[break_i]}")
    #     for j in range(break_i+1,n):
    #         if nums[j] < nums[break_i]: # swap i with j-1
    #             temp = nums[j-1]
    #             nums[j-1] = nums[break_i]
    #             nums[break_i] = temp
    #             break
    #     else: # if the loop breaks it will not be executed: swap i with n-1
    #         temp = nums[n-1]
    #         nums[n-1] = nums[break_i]
    #         nums[break_i] = temp
    #         # print(f"After swap - {nums}")
    #     # sort every thing after break_i
    #     # print(f"{nums[:break_i+1]}, {sorted(nums[break_i+1:])}")
    #     output = nums[:break_i+1] + sorted(nums[break_i+1:])
    #     return output
    
    def getPermutation(self, n: int, k: int) -> str:
        # recursive approach - first determine the first digit
        fact = self.calcFactorial(n)
        nums = [i for i in range(1,n+1)]
        output = []
        self.findNext(n,k-1,output,fact,nums)
        return "".join([str(c) for c in output])
    
    def findNext(self,n,k,output,fact,nums):
        # find first digit
        if k == 0:
            output.extend(nums)
            return
        if n == 1:
            output.append(nums[0])
            return
        firstIdx = k//fact[n-1]
        output.append(nums[firstIdx])
        nums.pop(firstIdx)
        k = k % fact[n-1]
        self.findNext(n-1,k,output,fact,nums)
    def calcFactorial(self,n):
        fact = [1]
        for i in range(1,n+1):
            fact.append(fact[i-1]*i)
        return fact

                 
                    
                
            

28600