LeetCode–第k个排列
<!-- more -->
博客阐明
文章所波及的材料来自互联网整顿和集体总结，意在于集体学习和教训汇总，如有什么中央侵权，请分割自己删除，谢谢！
介绍
60. 第k个排列
题目
给出汇合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小程序列出所有排列状况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"给定 n 和 k，返回第 k 个排列。
阐明：
给定 n 的范畴是 [1, 9]。给定 k 的范畴是[1, n!]。示例 1:
输出: n = 3, k = 3输入: "213"示例 2:
输出: n = 4, k = 9输入: "2314"思路
深度优先搜寻（DFS）+ 剪枝
深度优先搜寻： 能够了解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜寻，以此类推。
剪枝： 在搜寻中，遇到 这条路不可能和指标字符串匹配胜利 的状况（例如：此矩阵元素和指标字符不同、此元素已被拜访），则应立即返回，称之为 可行性剪枝 。
步骤
如果 kk 大于这一个分支将要产生的叶子结点数，间接跳过这个分支，这个操作叫「剪枝」
如果 kk 小于等于这一个分支将要产生的叶子结点数，那阐明所求的全排列肯定在这一个分支将要产生的叶子结点里，须要递归求解
代码
class Solution { public String getPermutation(int n, int k) { //初始化阶乘数组 int[] factorial = new int[n+1]; calculateFactorial(factorial,n); //查找全排列的布尔数组 boolean[] temp = new boolean[n+1]; Arrays.fill(temp,false); //动静字符串 StringBuilder path = new StringBuilder(); dfs(temp,factorial,0,path,k,n); return path.toString(); } private void dfs(boolean[] temp,int factorial[],int index,StringBuilder path,int k,int n){ if(index == n){ return; } //全排列个数 int cnt = factorial[n-1-index]; for(int i = 1; i <= n; i++){ if(temp[i]){ continue; } //过后全排列个数 if(cnt < k){ k -= cnt; continue; } path.append(i); temp[i] = true; dfs(temp,factorial,index+1,path,k,n); return; } } //计算阶乘数组 private void calculateFactorial(int[] factorial, int n){ factorial[0] = 1; for(int i = 1; i <= n; i++){ factorial[i] = factorial[i-1]*i; } }}感激
Leetcode以及勤奋的本人，集体博客，GitHub