Give the set [1,2,3,... N], all its elements have n! Species arrangement.

List all permutations in order of size and mark them one by one. When n = 3, all permutations are as follows:

"123"
"132"
"213"
"231"
"312"
"321"
Given n n n and k, return the kth permutation.

Explain:

The range of given n is [1, 9].
The range of given k is [1, n!].
Example 1:

Input: n = 3, k = 3
 Output: "213"
Example 2:

Input: n = 4, k = 9
 Output: "2314"

Source: LeetCode
 Link: https://leetcode-cn.com/problems/permutation-sequence
 Copyright belongs to the seizure network. For commercial reprints, please contact the official authorization. For non-commercial reprints, please indicate the source.

Train of thought: Backtracking method, find the arrangement of line k.

	int step = 0;
    String result="";
    public String getPermutation(int n, int k) {
        boolean[] adj = new boolean[n];
        StringBuilder sb=new StringBuilder();
        dfs(n, k, adj, sb);
        return result;
    }


    public void dfs(int n, int k, boolean[] adj,StringBuilder string) {

        for (int i = 0; i < n; i++) {
        	//Exit condition, and output the result to result when k rows are found.
            if (string.length() == n) {
                step++;
                if (step == k)result = string.toString();
                return;
            }
            if (adj[i] == true) continue;
            //You don't have to judge when you find k rows.
            if (step < k) {
                string.append(i + 1);
                adj[i] = true;
                dfs(n, k, adj, string);
                adj[i] = false;//To flash back
                string.deleteCharAt(string.length()-1);
            }
        }
        return;
    }

Idea 2: Using Mathematical Method to Deduce Arrangement Rows (Not Mastered)

public String getPermutation(int n, int k) {
        StringBuilder stringBuilder = new StringBuilder();
        k--;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i + 1);
        }
        while (!list.isEmpty()) {
            int fun = func(n-- - 1);
            stringBuilder.append(list.get(k / fun));
            list.remove(k / fun);
            k %= fun;
        }
        return stringBuilder.toString();

    }

    public int func(int n) {
        if (n == 1 || n == 0)
            return 1;
        return func(n - 1) * n;
    }