[Leetcode] Permutation Sequence

Problem

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):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Algorithm

Consider the most significant digit (msd) of the permutation. Let msd = 1, there are(n-1) digits left. Therefore, there are (n-1)! different sequences starting with 1. In another word, if 1<= k <= (n-1)!, the msd must be 1. Generally, the msd = (k-1) / (n-1)! + 1. When the first digit is determined, we can recursively determine the next msd. Of cause , the used digits are not available. 

In the code below, 

1. we build a factorial table in advance for fast look up. 

2. we use a boolean array to mark the visited numbers. 

Code