public String getPermutation(int n, int k) {
        int [] facts = new int[n+1];
        ArrayList<Integer> rms = new ArrayList<Integer>();
        rms.add(1);
        facts[0] = 1;
        for(int i = 1; i <= n-1; ++i){
            facts[i] = facts[i-1] * i;
            rms.add(i+1);
        }
        facts[n] = n * facts[n-1];
        if(k > facts[n]) return "";
        StringBuilder res = new StringBuilder();
        --k;
        for(int i = n-1; i >= 1; --i){
            int f = facts[i];
            res.append(rms.remove(k / f));
            k %= f;
        }
        res.append(rms.get(0));
        return res.toString();
    }