题目描述

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

Golang代码实现

func getPermutation(n int, k int) string {
    nums := make([]int,0)
    flags := make([]bool,n)
    for i:=1; i<=n; i++ {
        nums = append(nums, i)
    }

    return getPermutationBackTrace(nums,flags,"",n,k,0)
}

func getPermutationBackTrace(nums []int,flags []bool,cur string,n int,k int,depth int) string{
    if len(cur) == n{
        return cur
    }
    curMax := compute(n-depth-1)

    for i:=0; i<len(nums);i++{
        if flags[i]{
            continue
        }
        if curMax<k {
            k -= curMax
            continue
        }
        flags[i] = true
        return getPermutationBackTrace(nums,flags,cur+strconv.Itoa(nums[i]),n,k,depth+1)
    }
    return ""
}

func compute(n int) int {
    res := 1
    for i:=n; i>0; i-- {
        res *= i
    }
    return res
}