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 for n = 3:
- "123"
- "132"
- "213"
- "231"
- "312"
- "321"
Given n and k, return the kth permutation sequence.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
Example 3:
Input: n = 3, k = 1
Output: "123"
Constraints:
- 1 <= n <= 9
- 1 <= k <= n!
class Solution {
public String getPermutation(int n, int k) {
List<Integer> num = new LinkedList<Integer>();
for (int i = 1; i <= n; i++) num.add(i);
int[] fact = new int[n]; // factorial
fact[0] = 1;
for (int i = 1; i < n; i++){
fact[i] = i*fact[i-1];
}
k = k-1;
StringBuilder sb = new StringBuilder();
for (int i = n; i > 0; i--){
int ind = k/fact[i-1];
k = k%fact[i-1];
sb.append(num.get(ind));
num.remove(ind);
}
return sb.toString();
}
}