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

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

Given n and k, return the kth permutation sequence.

Solution: for n numbers, the permutations can be divided to (n-1)! groups, for n-1 numbers can be divided to (n-2)! groups, and so on. Thus k/(n-1)! indicates the index of current number, and k%(n-1)! denotes remaining index for the remaining n-1 numbers. k = k-1 would avoid dealing with case k%(n-1)!==0.

比如：n = 4, you have {1, 2, 3, 4}，找k = 14th个

If you were to list out all the permutations you have

1 + (permutations of 2, 3, 4)

2 + (permutations of 1, 3, 4)

3 + (permutations of 1, 2, 4)

4 + (permutations of 1, 2, 3)

k-- == 13, 13 / 3! == 2，说明第一个数字是index = 2的3. 然后k = 13 % 3! = 1，The permutations of {1, 2, 4} would be:

1 + (permutations of 2, 4)

2 + (permutations of 1, 4)

4 + (permutations of 1, 2)

1 / 2! == 0，说明第二个数字是index = 0的1，然后k = 1 % 2! = 1，继续下去。

    public String getPermutation(int n, int k) {
        int factorial = 1;
        List<Integer> nums = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i < n) {
                factorial *= i; //(n - 1)!
            }            
            nums.add(i);
        }
        k--;
        for (int i = n; i > 0; i--) {
            int index = k / factorial;
            sb.append(nums.get(index));
            nums.remove(index);
            k %= factorial;
         //或者写成 k -= index * factorial;
            if (i > 1) {
                factorial /= (i - 1); //注意排除i == 1时
            }            
        }
        return sb.toString();
    }