☆打卡算法☆LeetCode 60、排列序列 算法解析

示例 1：
输入： n = 3, k = 3
输出： "213"

示例 2：
输入： n = 4, k = 9
输出： "2314"

public class Solution {
    public int[] factor = new int[]{1,1,2,6,24,120,720,5040,40320,362880};
    public string GetPermutation(int n, int k) {
        StringBuilder path = new StringBuilder();
        bool[] visited = new bool[n + 1];
        dfs(n, k, 0, visited, path);
        return path.ToString();
    }

    private void dfs(int n, int k, int depth, bool[] visited, StringBuilder path){
        if(depth == n){
            return;
        }

        int fac = factor[n - 1 - depth];
        for(int i = 1; i <= n; i++){
            if(visited[i] == false){
                //当k大于可生成的叶子节点数，剪枝
                if(k > fac){
                    k -= fac;
                    continue;
                }
                path.Append(i.ToString());
                visited[i] = true;
                dfs(n, k, depth+1, visited, path);
                return;
            }
        }
    }
}