# 0060. Permutation Sequence

<https://leetcode.com/problems/permutation-sequence>

## Description

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

1. `"123"`
2. `"132"`
3. `"213"`
4. `"231"`
5. `"312"`
6. `"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!`

## ac: Math

```java
class Solution {
    public String getPermutation(int n, int k) {
        int[] permutationCount = new int[n+1]; // How many permutations if there are i number: {1, 1, 2, 6, 24, ... n!}
        permutationCount[0] = 1; // 0! is 1.
        int sum = 1;
        for (int i = 1; i <= n; i++) {
            sum *= i;
            permutationCount[i] = sum;
        }
        
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            nums.add(i);
        }
        
        StringBuilder res = new StringBuilder();
        k--; // Find kth -> index is (k-1)
        for (int i = 0; i < n; i++) {
            int lenOfPermutationAfterITh = n - i - 1; // "-1" because we don't include ith number.
            // What is the number in ith position, in the answer string. 
            // There are n-i numbers make up of permutationCount[n-i] candidates.
            int ithNumIndex = k / permutationCount[lenOfPermutationAfterITh];
            res.append(nums.get(ithNumIndex));
            
            nums.remove(ithNumIndex); // This number won't appear in the later part of the permutation.
            
            k = k % permutationCount[lenOfPermutationAfterITh]; // Already found 
        }
        
        return res.toString();
    }
}

// list.remove() is O(n), so time complexity is O(N^2). The brute force is O(KNlogN), if K is large, it is bad.
// This is more of a math problem.
```