> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/tips/60.-permutation-sequence.md).

# 60. Permutation Sequence

{% embed url="<https://leetcode.com/problems/permutation-sequence/>" %}

`permutation 這類的題目主要有三種`

1. `全排列 permutation`

[`https://leetcode.com/problems/permutations/`](https://leetcode.com/problems/permutations/)

[`https://leetcode.com/problems/permutations-ii/`](https://leetcode.com/problems/permutations-ii/)

`2.  kth permutation`

[`https://leetcode.com/problems/permutation-sequence/`](https://leetcode.com/problems/permutation-sequence/)

3\.  next `permutation`

[`https://leetcode.com/problems/next-permutation/`](https://leetcode.com/problems/next-permutation/)

## `kth permutation`

<http://bangbingsyb.blogspot.com/2014/11/leetcode-permutation-sequence.html>

1. `"123"`
2. `"132"`
3. `"213"`
4. `"231"`
5. `"312"  => 5th`
6. `"321"`

`1 =>  後兩位的排列數, 即 2! = 2*1  , 即`f(n-1) 代表後面階層會經過的序列

`123`

`132`

`2 =>`&#x20;

`213`

`231`

`3 =>`&#x20;

`312`

`321`

nums = \[1, 2, 3]; // 儲存了要排列的數字

所以要得到第一位是什麼數字, &#x20;

k--; // 化為起始 0 開始的序列 // k = 4

k = k / f(n-1) // 這樣就會得到第一位的 index

k = 4/2 = 2, index 2 =  nums\[2] = 3

k = k % f(n-1); // 下輪要繼續跑的數字, 即  k 減掉 我們剛剛pass過的序列

O(n^2), nums.remove(), 需要O(n)

but Given *n* will be between 1 and 9 inclusive.

so time complexity is small

space complexity: O(n)

```java
class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder sb = new StringBuilder();
        int[] f = new int[n];
        List<Integer> nums = new ArrayList<>();
        f[0] = 1;
        
        
        for (int i = 1 ; i < n ; i++) {
            f[i] = i*f[i-1];
            nums.add(i);
        }
        nums.add(n);
        k--;
        
        for (int i = n; i > 0; i--) {
            int idx = k/f[i-1];  
            k = k % f[i-1];
            sb.append(nums.get(idx));
            nums.remove(idx);
        }
        return sb.toString();
    }
}
```