How to solve the k th permutation problem of LeetCode

Editor to share with you LeetCode how to solve the k ranking problem, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

Title

Give the set [1pm 2pm 3, … , n], whose elements all share n! Species arrangement.

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

"123"132"213"231"312"321"

Given n and k, return the k th permutation.

Description: the range of a given n is [1,9]. The range of a given k is [1, n!]. Example 1: input: n = 3, k = 3 output: "213" example 2: input: n = 4, k = 9 output: "2314" idea

Depth first search (DFS) + pruning

Depth-first search: can be understood as brute force traversal of all string possibilities in the matrix. DFS searches in one direction through recursion, then goes back to the previous node, searches in the other direction, and so on.

Pruning: in the search, when it is impossible for this path to match the target string (for example, this matrix element is different from the target character and this element has been accessed), it should be returned immediately, which is called feasible pruning.

Steps

If the kk is greater than the number of leaf nodes that this branch will produce, skip the branch directly. This operation is called "pruning".

If kk is less than or equal to the number of leaf nodes that this branch will produce, it means that the full permutation must be in the leaf nodes that this branch will produce, and it needs to be solved recursively.

The code class Solution {public String getPermutation (int n, int k) {/ / initializes the factorial array int [] factorial = new int [nyst1]; calculateFactorial (factorial,n); / / finds the fully arranged Boolean array boolean [] temp = new boolean [nyst1]; Arrays.fill (temp,false); / / dynamic string StringBuilder path = new StringBuilder () Dfs (temp,factorial,0,path,k,n); return path.toString ();} private void dfs (boolean [] temp,int factorial [], int index,StringBuilder path,int kline int n) {if (index = = n) {return;} / / the number of full permutations int cnt = factorials [n-1-index]; for (int I = 1; I