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

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


	"123"
	"132"
	"213"
	"231"
	"312"
	"321"


Given n and k, return the kth permutation sequence.

&nbsp;
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
Example 3:
Input: n = 3, k = 1
Output: "123"

&nbsp;
Constraints:


	1 &lt;= n &lt;= 9
	1 &lt;= k &lt;= n!


  class Solution:
    def nextPermutation(self, nums: List[int]):
        n = len(nums)
        high = n-1
        low = -1
        for i in range(n-1, 0, -1):
            if nums[i] > nums[i-1]:
                low = i-1
                break
        if low == -1:
            nums[low+1:] = reversed(nums[low+1:])
            return
        for i in range(n-1, low, -1):
            if nums[low] < nums[i]:
                nums[low], nums[i] = nums[i], nums[low]
                break
        nums[low+1:] = reversed(nums[low+1:])
        return nums

    def getPermutation(self, n: int, k: int) -> str:
        s = ["1","2","3","4","5","6","7","8","9"]
        s = s[:n]
        if k==1:
            return ''.join(s)
        dic = {1:1,2:2,3:6,4:24,5:120,6:720,7:5040,8:40320,9:362880}        
        if k==dic[n]:
            return ''.join(s)[::-1]
        x = 0
        while k>dic[n-1]:
            k -= dic[n-1]
            x += 1
        y=[]
        y.append(s[x])
        for i in range(n):
            if i==x:
                continue
            y.append(s[i])
        while k!=1:
            self.nextPermutation(y)
            k-= 1
        y = ''.join(y)
        return y
class Solution {
    public String getPermutation(int n, int k) {
        int fact = 1;
        List<Integer> nums = new ArrayList<>();
        for(int i = 1; i<n; i++){
            fact = fact * i;
            nums.add(i);
        }
        nums.add(n); // Add last permutation number.
        String res = "";
        k = k - 1; // We use 0 indexing.
        while(true){
            res = res + nums.get(k / fact); 
            nums.remove(k / fact); 
            if(nums.size() == 0) break;
            
            k = k % fact;
            fact = fact / nums.size();
        }
        return res;
    }
}
class Solution {
public:
    string getPermutation(int n, int k) {
        int fact=1;
        vector<int> numbers;
        for(int i=1;i<n;i++){
            fact=fact*i;
            numbers.push_back(i);
        }
        numbers.push_back(n);
        string ans="";
        k=k-1;
        while(true){
            ans=ans+to_string(numbers[k/fact]);
            numbers.erase(numbers.begin()+(k/fact));
            if(numbers.size()==0) break;
            k=k%fact;
            fact=fact/numbers.size();
        }
        return ans;
    }
};
const dfs = (path, visited, result, numbers, limit) => {
    // return if we already reached the permutation needed
    if(result.length === limit) {
        return;
    }
    
    // commit the result
    if(path.length === numbers.length) {
        result.push(path.join(''))
        return;
    }
    
    // easier to reason and less prone to miss the -1 offset of normal for loop
    for(const [index, number] of numbers.entries()) {
        if(visited[index]) continue;
        
        path.push(number);
        visited[index] = true;
        dfs(path, visited, result, numbers);
        path.pop();
        visited[index] = false;
    }
}

var getPermutation = function(n, k) {
    const numbers = Array.from({length: n}, (_, i) => i + 1);
    let visitedNumbers = Array.from(numbers, () => false);
    let result = [];
    dfs([], visitedNumbers, result, numbers, k);
    return result[k - 1];
};
Permutation Sequence