Formula Solution - Permutation Sequence - permutation **

The idea is to base on the index to calculate the corresponding permutation. The list is pre set and removed after using the index, since the same index would be used every loop. The mod is initialized to be all n!, and then update by being divided by n to 1, and k is updated to be the remaining.

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

// initialize all numbers
ArrayList<Integer> numberList = new ArrayList<Integer>();
for (int i = 1; i <= n; i++) {
numberList.add(i);
}

// change k to be index
k--;

// set factorial of n
int mod = 1;
for (int i = 1; i <= n; i++) {
mod = mod * i;
}

StringBuilder result = new StringBuilder();

// find sequence
for (int i = 0; i < n; i++) {
mod = mod / (n - i);
// find the right number(curIndex) of
int curIndex = k / mod;
// update k
k = k % mod;

// get number according to curIndex
result.append(numberList.get(curIndex));
// remove from list
numberList.remove(curIndex);
}

return result.toString();
}
}