题解 | #第K个n的排列#

import java.util.*;

public class Solution {

//这是一道递归排列组合的题目，要求就是组合的字符不能重复
public String KthPermutation (int n, int k) {
    // write code here
    boolean[] isUsed = new boolean[n];
    StringBuilder stringBuilder = new StringBuilder();
    ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
    LinkedList<Integer> linkedList = new LinkedList<>();
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        list.add(i);
    }
    computeArray(n,list,linkedList,arrayLists,0,isUsed);
    list = arrayLists.get(k-1);
    for (Integer integer : list) {
        stringBuilder.append(integer);
    }
    return stringBuilder.toString();
}

private void computeArray(int length, ArrayList<Integer> list, LinkedList<Integer> linkedList, ArrayList<ArrayList<Integer>> arrayLists,int depth,boolean[] isUsed) {
    if(depth==length){
        arrayLists.add(new ArrayList<>(linkedList));
        return;
    }
    for (int j = 0; j < list.size(); j++) {
        if(isUsed[j]){
            continue;
        }
        if(j>0&&list.get(j).equals(list.get(j-1))&&!isUsed[j-1]){
            continue;
        }
        linkedList.add(list.get(j));
        isUsed[j]=true;
        computeArray(length,list,linkedList,arrayLists,depth+1,isUsed);
        linkedList.removeLast();
        isUsed[j]=false;
    }
}

}