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.
Note:
Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
Solutions:
class Solution {
public String getPermutation(int n, int k) {
StringBuilder sb = new StringBuilder();
boolean[] used = new boolean[n + 1];
backtrack(sb, k, n, used);
return sb.toString();
}
private void backtrack(StringBuilder sb, int k, int n, boolean[] used) {
if (sb.length() == n) return;
else {
int times = 1;
int factorial = factorial(n - 1 -sb.length());
for (int i = 1; i <= n; i++) {
if (used[i]) continue;
else {
if (k <= times factorial) {
sb.append(i);
used[i] = true;
backtrack(sb,k - (times - 1) factorial,n,used);
}
else times++;
}
}
}
}
private int factorial (int n) {
int res = 1;
while (n > 1) {
res *= n;
n--;
}
return res;
}
}
Points:
Here we have an upgraded version of backtracking template. FIrstly, unique to this problem is to set a factorial method to calculate the value of the factorial given a certain number. Something universal is to add a used boolean array to avoid duplicates. Another iteration variable here is the times function each time we do a backtracking, checking which part of the remaining numbers belong.
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.
Note:
Given n will be between 1 and 9 inclusive. Given k will be between 1 and n! inclusive. Example 1:
Input: n = 3, k = 3 Output: "213" Example 2:
Input: n = 4, k = 9 Output: "2314"
Solutions: class Solution { public String getPermutation(int n, int k) { StringBuilder sb = new StringBuilder(); boolean[] used = new boolean[n + 1]; backtrack(sb, k, n, used); return sb.toString(); } private void backtrack(StringBuilder sb, int k, int n, boolean[] used) { if (sb.length() == n) return; else { int times = 1; int factorial = factorial(n - 1 -sb.length()); for (int i = 1; i <= n; i++) { if (used[i]) continue; else { if (k <= times factorial) { sb.append(i); used[i] = true; backtrack(sb,k - (times - 1) factorial,n,used); } else times++; } } } }
}
Points: