Given n and k, return the kth permutation sequence.

getPermutation.java

/*
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):

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
*/
public class Solution {
    ArrayList<String> permuteList = new ArrayList<String>();
    private boolean[] used;
    private StringBuilder prefix = new StringBuilder();
    public String getPermutation(int n, int k) {
        // Start typing your Java solution below
        // DO NOT write main() function
        permuteList.clear();
        prefix.delete(0,prefix.length());
        used = new boolean[n];
        char[] origin = new char[n];
        build_str(origin, n);
        
        build_permute(n, origin);
        
        String[] list = permuteList.toArray(new String[permuteList.size()]);
        
        Arrays.sort(list);
        if (k <= list.length)
            return list[k-1];
        else
            return null;
    }
    
    public void build_str(char[] origin, int size) {
        for(int i = 1, j = 0; i <= size; i++, j++) {
            origin[j] = (char) ('0'+i);
        }
    }
    
    public void build_permute(int size, char[] origin) {
        if (prefix.length() == size) {
            permuteList.add(prefix.toString());
            return;
        }
            
        for(int i = 0; i < size; i++) {
            if(used[i]) continue;
            prefix.append(origin[i]);
            used[i] = true;

            build_permute(size, origin);
            
            used[i] = false;
            prefix.setLength(prefix.length() - 1);
        }
        
        return;
    }
}