Question:

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

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

Given n and k, return the kth permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive. ``` Example 1:

Input: n = 3, k = 3 Output: “213”

Example 2:

Input: n = 4, k = 9 Output: “2314”


### Thinking:
* Method:
	* 使用backtrace，很慢，O(n!)

```Java
class Solution {
    public String getPermutation(int n, int k) {
        if(n <= 0 || k <= 0) return null;
        int[] nums = new int[n];
        for(int i = 0; i < n; i++)
            nums[i] = i + 1;
        List<List<Integer>> result = new ArrayList<>();
        backtrace(nums, new ArrayList<Integer>(), n, result, new boolean[n], k);
        StringBuilder sb = new StringBuilder();
        List temp = result.get(result.size() - 1);
        for(int i = 0; i < n; i++)
            sb.append(temp.get(i));
        return sb.toString();
    }
    private static void backtrace(int[] nums, List<Integer> list, int n, List<List<Integer>> result, boolean[] used, int k){
        if(list.size() == n){
            result.add(new ArrayList<Integer>(list));
            if(result.size() == k)
                return;
        }else{
            if(result.size() == k)
                return;
            for(int i = 0; i < n; i++){
                if(used[i]) continue;
                list.add(nums[i]);
                used[i] = true;
                backtrace(nums, list, n, result, used, k);
                used[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}

二刷

二刷的结果更恶心了，时间变长。

class Solution {
    int count = 0;
    public String getPermutation(int n, int k) {
        List<String> result = new LinkedList<>();
        backtrace(result, new StringBuilder(), n, k, new boolean[n + 1]);
        return result.get(0);
    }
    private void backtrace(List<String> result, StringBuilder sb, int n, int k, boolean[] used){
        if(count >= k) return;
        if(sb.toString().length() == n){
            if(++count == k)
                result.add(sb.toString());
        }else{
            for(int i = 1; i <= n; i++){
                if(!used[i]){
                    sb.append(i);
                    used[i] = true;
                    backtrace(result, sb, n, k, used);
                    used[i] = false;
                    sb.deleteCharAt(sb.toString().length() - 1);
                }
            }
        }
    }
}