60 Permutation Sequence

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 (ie, for n= 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k th permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

思路：还是用backtrace，和Permutation差不多

public class Solution {
    public String getPermutation(int n, int k) {
        int[] arr = new int[n];
        for (int i=0;i<n;i++){
            arr[i] = i+1;
        }
        List<String> res = new ArrayList<String>();
        StringBuilder temp = new StringBuilder();
        backtrace(res,arr,temp,n,k,0);

        return res.get(k-1);
    }

    public void backtrace(List<String> res,int[] arr,StringBuilder temp, int n, int k, int times){
        if (temp.length()==n){
            res.add(temp.toString());
            times++;
            return;
        }

        if (times==k) return;

        for (int i=0;i<arr.length;i++){
            if (temp.indexOf(String.valueOf(arr[i])) != -1) continue;
            temp.append(arr[i]);
            backtrace(res,arr,temp,n,k,times);
            temp.deleteCharAt(temp.length()-1);
        }
    }
}