Leet_Permu_Lex

  public static String s = "";

    public String getPermutation(int n, int k) {
        int[] nums = generateArray(n);
        backtrack(nums, 0, k);

        return s;

    }

    static int c = 0;

    private static void backtrack(int[] nums, int i, int k) {

        if (i == nums.length) {
            if (++c == k) {
                for (int m : nums) {
                    s += String.valueOf(m);
                }
                System.out.println(s);
            }
        }
        for (int j = i; j <= nums.length - 1; j++) {
            rtRotate(nums, i, j);
            backtrack(nums, i + 1, k);
            ltRotate(nums, i, j);
        }


    }

    public static void rtRotate(int[] array, int start, int end) {
        reverse(array, start, end);
        reverse(array, start, start);
        reverse(array, start + 1, end);
    }

    public static void ltRotate(int[] array, int start, int end) {
        reverse(array, start, start);
        reverse(array, start + 1, end);
        reverse(array, start, end);
    }

    private static void reverse(int[] array, int start, int end) {
        while (start < end) {
            int temp = array[start];
            array[start] = array[end];
            array[end] = temp;
            start++;
            end--;
        }
    }

    public static int[] generateArray(int n) {
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = i + 1;
        }
        return array;
    }