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

By listing and labeling all of the permutations in order,
We get the following sequence (ie, forn= 3):

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

Givennandk, return thekthpermutation sequence.

Note:Givennwill be between 1 and 9 inclusive.

class Solution {
    public String getPermutation(int n, int k) {
        int[] factors = new int[n + 1];
        factors[0] = 1;
        int sum = 1;
        for (int i = 1; i <= n; i++){
            sum *= i;
            factors[i] = sum;
        }
        // 1 1 2 6 24

        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= n; i++){
            numbers.add(i);
        }
        // 1 2 3 4

        k--;
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++){
            int index = k / factors[n - i];
            sb.append(String.valueOf(numbers.get(index)));
            numbers.remove(index);
            k -= index * factors[n - i];
        }

        return sb.toString();
    }
}