# [60\. Permutation Sequence](https://leetcode.com/problems/permutation-sequence/)

Permutation 的特性，以一個 n = 3 的例子來說，左邊數來第一個位置，每個數字會出現 2 次，左邊數來的第 2 個位置，每個數字出現 1 次，左邊數來的第 3 個位置，每個數字出現 1 次
- 123
- 132
- 213 <- k = 3
- 231
- 312
- 321

class Solution {
public:
    string getPermutation(int n, int k)
    {   
        // 計算每個數字的階乘的結果，將其保存在 factorials 中。
        vector<int> factorials(n, 1);
        
        // 使用一個 loop 從 1 開始，計算階層
        // factorials 會是 [1, 1, 2, 6, 24, 120, 720, 5040, 40320]
        //                [0!, 1!, 2!, 3!, 4!, 5!, 6!, 7!, 8!, 9!]        
        for (int i = 1; i < n; ++i)
        {
            factorials[i] = factorials[i - 1] * i;
        }

        // k - 1，因為 index 是從 0 開始的
        --k;

        string res;   
        string num = "123456789";
        
        // 從 n 開始遞減到 1
        for (int i = n; i >= 1; --i)
        {
            // j 代表當前數字在結果中的位置
            int j = k / factorials[i - 1];

            // 取餘數
            k %= factorials[i - 1];
            
            // 從 num 中取出第 j 個數字，推到 res 中
            res.push_back(num[j]);
            // 從 num 消去已經使用過的數字
            num.erase(j, 1);
        }
        return res;
    }
};

:::success
- 時間複雜度：$O(n^2)$
- 空間複雜度：$O(n)$
:::