共计 848 个字符，预计需要花费 3 分钟才能阅读完成。
题目地址：https://leetcode-cn.com/probl… 题目描述：给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
“123””132″”213″”231″”312″”321″ 给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。给定 k 的范围是 [1, n!]。示例 1:
输入: n = 3, k = 3 输出: “213” 示例 2:
输入: n = 4, k = 9 输出: “2314”
解答：两种解法：第一种是利用求下一个排列来求，先排序然后调用 k - 1 次下一个排列。第二种是回溯法求全排列，设置一个全局变量 cur 为当前求出的排列数，求出第 k 个全排列，也就是 cur== k 时，停止所有递归 (否则会超时)。虽然基于交换递归的方法也可以求全排列，但是那种方法求的没有序的关系，所以只能回溯，而不能用递归的方法。我这里采用第二种方法。java ac 代码：
class Solution {
int cur = 0;
String ans = “”;
public String getPermutation(int n, int k) {
int[]nums = new int[n];
for(int i = 0;i < n;i++){
nums[i] = i+1;
}
backtrack(0,n,k,nums,new int[n],new boolean[n]);
return ans;
}
void backtrack(int i,int n,int k,int[] nums,int[] A,boolean[]flag)
{
if(cur == k)
return;
if(i == n)
{
cur++;
if(cur == k)
for(int j = 0;j < A.length;j++)
ans+=A[j];
return;
}
for(int j = 0;j < nums.length;j++)
if(!flag[j])
{
A[i] = nums[j];
flag[j] = true;
backtrack(i+1,n,k,nums,A,flag);
flag[j] = false;
}
}
}
