题目描述

给出集合 [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;
    }