题目描述
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
示例：
输入: 3
输出:
1."123"
2."132"
3."213"
4."231"
5."312"
6."321"
思路
1.最简单方法就是按照46.全排列计算出所有的情况，然后选取第K个元素，但是运行超时了。
2.我们可以进一步思考，既然是递归实现的，我们便可以对递归树进行剪枝，从而缩短其执行时间。
3.我们可以发现，假如有n个元素，我们选定了第一个元素，其可能产生的排列组合是(n-1)!个，所以我们可以根据阶乘和k的大小比较进行剪枝操作，若阶乘<k，便进行剪枝。
Java代码实现
public String getPermutation(int n, int k) {
List<Integer> nums = new ArrayList<>();
for (int i = 1; i <= n; i++) {
nums.add(i);
}
boolean[] flags = new boolean[n];
return backTraceNumStr(new StringBuffer(),nums,k,n,0,flags);
}
private String backTraceNumStr(StringBuffer res, List<Integer> nums, int k,int n,int depth,boolean[] flags){
if(depth == n){
return res.toString();
}
//该分支最多的组合数
int branchNum = factorial(n-1-depth);
for (int i =0; i < n; i++) {
if(flags[i]){
continue;
}
if(branchNum < k){
k -= branchNum;
continue;
}
res.append(nums.get(i));
flags[i] = true;
return backTraceNumStr(res,nums,k,n,depth+1,flags);
}
return null;
}
private int factorial(int n){
int res = 1;
for (int i = n; i > 0; i--) {
res *= i;
}
return res;
}
