class Solution {
    public String getPermutation(int n, int k) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        backtrace(nums, new StringBuilder(), k);
        return res.get(res.size() - 1);
    }

    private List<String> res = new ArrayList<>();
    private boolean max = false;

    public void backtrace(int[] nums, StringBuilder track, int k) {
        //结束条件
        if (track.length() == nums.length) {
            res.add(track.toString());
            if (res.size() == k) max = true;
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //剪枝
            if (max) return ;
            if (track.indexOf(String.valueOf(nums[i])) != -1) continue;
            //做选择
            track.append(nums[i]);
            //递归
            backtrace(nums, track, k);
            //撤销
            track.deleteCharAt(track.length() - 1);
        }
    }
}

class Solution {
    public String getPermutation(int n, int k) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        backtrace2(nums, new boolean[n], new StringBuilder(), k);
        return res;
    }

    private String res = "";    //优化一下空间，结果只存一个
    private int num = 0;
    public void backtrace2(int[] nums, boolean[] flag, StringBuilder track, int k){
        //结束条件
        if (track.length() == nums.length){
            res = track.toString();
            num++;
            return ;
        }
        for (int i = 0; i < nums.length; i++) {
            //剪枝
            if (k == num) return ;
            if (flag[i]) continue;
            //做选择
            track.append(nums[i]);
            flag[i] = true;
            //递归
            backtrace2(nums, flag, track, k);
            //撤销
            track.deleteCharAt(track.length() - 1);
            flag[i] = false;
        }
    }
}

public class six_zero_第k个排列_other {

    @Test
    public void test(){
        String res = getPermutation(4, 9);
        System.out.println(res);
    }

    public String getPermutation(int n, int k) {
        //生成排列数列表 paiLie[0] = 0! paiLie[1] = 1!  由排列公式可得n! = n * (n - 1)!
        int[] paiLie = new int[n + 1];
        List<Integer> nums = new LinkedList<>();    //选择列表，也就是1234，每次被选择一位后这里就会减少一位
        paiLie[0] = 1;
        for (int i = 1; i <= n; i++) {
            paiLie[i] = paiLie[i - 1] * i;  //n! = n * (n - 1)!
            nums.add(i);
        }
        //准备完毕，开始从左到右找到每一位
        String res = "";
        k--;    //这个可以回过头来看，因为下面k的计算是跟跳过的个数onceSkip相关的，onceSkip是下标，因此要先-1成下标
        while (nums.size() != 0){
            int onceSkip = paiLie[(nums.size() - 1)];   //也就是1开头的有6条，这就是这个6，当然第二位的时候就是(n - 1)!了
            int index = k / onceSkip;
            res += nums.get(index);
            //后面重复，nums变为少了当前加的这个值，k也会减去跳过的个数
            nums.remove(index);
            k -= index * onceSkip;  //总共跳过的条数
        }
        return res;
    }
}

public String getPermutation(int n, int k) {
    //生成排列数列表 paiLie[0] = 0! paiLie[1] = 1!  由排列公式可得n! = n * (n - 1)!
    int[] paiLie = new int[n + 1];
    List<Integer> nums = new LinkedList<>();    //选择列表，第一轮为1234
    paiLie[0] = 1;
    for (int i = 1; i <= n; i++) {
        paiLie[i] = paiLie[i - 1] * i;
        nums.add(i);
    }
    return "";
}