給出集合 [1,2,3,…,n]，其所有元素共有 n! 種排列耍群。
按大小順序列出所有排列情況，并一一標記找筝，當 n = 3 時, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
給定 n 和 k蹈垢，返回第 k 個排列

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/permutation-sequence
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權袖裕，非商業(yè)轉載請注明出處曹抬。

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時坎藐。第一次循環(huán)i=1.此時階乘為2!.也就說這個1開頭的排列有2個为牍。但是k>2所以哼绑。
                //所需要的不是前2個。所以跳過碉咆。并且將k=3-2.下次循環(huán)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;
        }
    }
}