60. Permutation Sequence

class Solution {
    public String getPermutation(int n, int k) {

        // n = 4, k = 14

        //{1, 1, 2, 6, 24}
        int[] factorial = new int[n + 1];
        //{1, 2, 3, 4}
        List<Integer> nums = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        factorial[0] = 1;
        int sum = 1;
        for (int i = 1; i <= n; i++){
            sum *= i;
            factorial[i] = sum;
        }

        for (int i = 1; i <= n; i++){
            nums.add(i);
        }

        k--;
        for (int i = 1; i <= n; i++){
            int index = k / factorial[n - i];
            sb.append(Integer.valueOf(nums.get(index)));
            nums.remove(index);
            k -= index * factorial[n - i];
        }

        return new String(sb);
    }
}