给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public class Solution {

    private int n;
    private int k;
    private int[] factorial;
    private bool[] used;
    private string result;

    public string GetPermutation(int n, int k) {
        this.n = n;
        this.k = k;
        Factorial(n);
        result = "";
        DFS(0, result);
        return result;
    }

    private void DFS(int index, string res){
        //index=0时将会选取到一个。所有在index=n时已经排列完毕
        if(index == n){
            return;
        }

        for(int i=1; i<=n; i++){
            int count = factorial[n-index-1];
            if(used[i]){
                //在里面说明这个数字已经在排列里里
                continue;
            }
            if(k>count){
                //当index=0时。将会取n-1.如果选取了一个。那么为1将会有n-1!个排列。
                //也就是说如果k大于n-1!个排列。说明k不在这个排列中。所以跳过这个数
                //举例n=3/k=3。那么刚开是index=0时。第一次循环i=1.此时阶乘为2!.也就说这个1开头的排列有2个。但是k>2所以。
                //所需要的不是前2个。所以跳过。并且将k=3-2.下次循环i=2。此时阶乘也为2!。但是k<2所以可以确定顺序排列在以2开头的位置.
                k -= count;
                continue;
            }
            used[i] = true;
            result = res + i.ToString();
            DFS(index+1, result);
            return;
        }
    }

    ///阶乘
    ///
    private void Factorial(int n){
        factorial = new int[n+1];
        used = new bool[n+1];
        factorial[0] = 1;
        used[0] = false;
        for(int i = 1; i<n; i++){
            factorial[i] = factorial[i-1] * i;
            used[i] = false;
        }
    }
}