LeetCode: Permutation Sequence

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.

public class Solution {
    public String getPermutation(int n, int k) {
        // Start typing your Java solution below
        // DO NOT write main() function
        boolean[] output = new boolean[n];
        StringBuilder buf = new StringBuilder("");
        int[] res = new int[n];
        res[0]=1;
        for(int i=1;i<n;i++)
            res[i]=res[i-1]*i;
        
        for(int i=n-1;i>=0;i--){
            int s=1;
            while(k>res[i]){
                s++;
                k-=res[i];
            }
            for(int j=0;j<n;j++){
                if(j+1<=s && output[j]){
                    s++;
                }
            }
            output[s-1]=true;
            buf.append(Integer.toString(s));
        }        
        return buf.toString();
    }
}