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

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

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Givenn_and_k, return the_k_thpermutation sequence.

Note:

• Given _n _will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

class Solution {
    public String getPermutation(int n, int k) {
        ArrayList<Integer> nums = new ArrayList<>();
        for(int i = 1; i <= n; i++) {
            nums.add(i);
        }
        k--;
        StringBuilder res = new StringBuilder();

        for(int i = 0; i < n; i++) {
            int index = k / getFactorial(n - 1 - i);
            System.out.println(nums.get(index));
            res.append(nums.remove(index));
            k -= index * getFactorial(n - 1 - i);
        }

        return res.toString();
    }

    public int getFactorial(int n) {
        if(n == 0)
            return 1;
        if(n == 1)
            return 1;

        int res = 1;
        for(int i = 1; i <= n; i++)
            res *= i;

        return res;
    }
}