leetcode：回溯——permutation-sequence，

1. permutation-sequence 顺序排列第k个序列

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):

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

Given n and k, return the k th permutation sequence.

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

第一位每个数字开头的序列都有（n-1）！个序列，因此n个数字所以共有n！个序列。以此类推，第二位每一个数开头都有（n-2）！个序列。

 

public class Solution {

    public String getPermutation(int n, int k) {

        // initialize all numbers

        ArrayList<Integer> numberList = new ArrayList<Integer>();

        for (int i = 1; i <= n; i++) {

            numberList.add(i);

        }

        // change k to be index

        k--;

        // set factorial of n

        int mod = 1;

        for (int i = 1; i <= n; i++) {

            mod = mod * i;

        }

        String result = "";

        // find sequence

        for (int i = 0; i < n; i++) {

            mod = mod / (n - i);

            // find the right number(curIndex) of

            int curIndex = k / mod;

            // update k

            k = k % mod;

            // get number according to curIndex

            result += numberList.get(curIndex);

            // remove from list

            numberList.remove(curIndex);

        }

        return result.toString();

    }

}