### Permutation Sequence

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 (ie, 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.

``````import java.util.*;
/**
* Created by gzdaijie on 16/5/26
*/
public class Solution {
public String getPermutation(int n, int k) {
int total = 1;
List<Integer> pool = new ArrayList<>();
StringBuilder result = new StringBuilder();

for (int i = 1; i <=n; i++) {
total *= i;
}

find(pool, result, total, k);
return result.toString();
}

private void find(List<Integer> pool, StringBuilder result, int total, int k) {
int n = pool.size();
if (n == 1) {
result.append(pool.get(0));
return;
}
// (k * n - 1)/total 可以计算出应该是多少打头，加入result后递归
int index = (k * n - 1) / total;
int t = pool.remove(index);
result.append(t);
find(pool, result, total/n, k - total/n * index);
}
}
``````
updated 2016-05-26 22:10:32