Permutation Sequence.java

public class Solution {
    public String getPermutation(int n, int k) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(k<0) return ""; 
        ArrayList<Integer>num=new ArrayList<Integer>();
        int sum=1; 
        for(int i=1; i<=n; i++)
        {
            sum*=i; num.add(i); 
        }
        StringBuffer sb=new StringBuffer();
        for(int i=n; i>0; i--)
        {
            sum=sum/i;
            int idx=(k-1)/sum; 
            sb.append(num.get(idx));
            num.remove(idx);
            k=k-idx*sum; 
        }
        return sb.toString();
    }
}