Question:

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 (ie, for n = 3):

“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Thinking:

We can conclude the position of the element in the searching tree according to the k. For example, there are n subtrees in the first level, so the k/(n-1) means picking the k/(n-1) th element in the array. And delete the element from the element, pick the next one. Do this recursively.

Solution:

public String getPermutation(int n, int k) {
    ArrayList<Integer> nums = new ArrayList<Integer>();
    int fac = 1;
    int[] pos = new int[n+1];
    for (int i = 1; i <= n; i++){
        nums.add(i);
        fac *= i;
    }
    fac /= n;
    k -= 1;
    for (int i = 1; i < n; i++){
        pos[i] = k / fac;
        k %= fac;
        fac /= (n-i);
    }
    StringBuilder res = new StringBuilder();
    for (int i = 1; i <= n; i++){
        res.append(nums.remove(pos[i]));
    }

    return res.toString();
}