第k个排列

QUESTION:

给出集合 [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”

EXPLANATION:

其实如果写过全排列的那道题，其实这道题就比较简单了。只要拿到之前的结果，然后再进行get到第k个结果就可以。采用回溯算法就ok。
思路：
1.创建一个数组来表示已经取到的n
2.循环遍历，采用递归的方式来进行遍历，并记录在tmp中
3.如果tmp的长度正好是n的长度，那么就说明都遍历完了，加入到结果集中
4.由于本道题目不需要完成所有的遍历。所以在进行到k的时候，就可以结束了
5.返回结果集中的第k个值

SOLUTION:

class Solution {
    public String getPermutation(int n, int k) {
        boolean[] anchors = new boolean[n+1];
        anchors[0] = true;
        ArrayList<String> strings = new ArrayList<>();
        getPermutationHelper(n,k,strings,anchors,"");
        return strings.get(k-1);
    }
    
    public static void getPermutationHelper(int n, int k,List<String> strings,boolean[] anchors,String tmp) {
        if(tmp.length()==n){
            strings.add(tmp);
        }
        if(strings.size()<k){
            for(int i = 0;i<n+1;i++){
                if(!anchors[i]){
                    anchors[i] = true;
                    tmp = tmp+i;
                    getPermutationHelper(n,k,strings,anchors,tmp);
                    tmp = tmp.substring(0,tmp.length()-1);
                    anchors[i] = false;
                }
            }
        }
    }
}
--> return <--