主題
題目連結：
題目意譯：
集合 [1, 2, 3, …, n] 包含著總計 n! 種相異排列。
藉由依序列舉並編號所有的排列方式，我們得到下列序列（對於 n = 3）：
"123"
"132"
"213"
"231"
"312"
"321"
給定 n 和 k，回傳第 k 個排列。
限制：
1 ≦ n ≦ 9
1 ≦ k ≦ n!
範例測資：
範例 1：
輸入： n = 3, k = 3
輸出： "213"
範例 2：
輸入： n = 4, k = 9
輸出： "2314"
範例 3：
輸入： n = 3, k = 1
輸出： "123"
解題思維：
跟往常的排列組合題型（如這題）很類似。不過這次是反過求第 k 個排列，而不是給你排列本身求出 k 值為何。
以範例 2 的 n = 4 、 k = 9 為例：
現在我們想要確定第一個數字是什麼，所以我們就來看看 k = 9 位在哪個開頭的排列可能之中。
開頭 1 有 3! = 6 種排列。而 6 < 9，所以不會是 1 開頭的、
開頭 2 加上前面的開頭 1，總計有 2 × 3! = 12 種排列。而 12 ≧ 9，所以我們的目標排列是以 2 開頭的。
接著我們把 k 減去 3!（開頭 1 的排列數），因為我們現在想要知道在以 2 開頭的情況下目標排列是第幾個排列?？廴デ懊娴呐帕袛抵?，我們便可以忽略數字 2，然後將問題變成「現在有 1 、 3 、 4 這 3 個數字，其第 3 個排列為何」。
接著就重複著與上面類似的步驟便可以確認每一位數應為哪個數字。以下就把上面的例子跑完：
開頭 1（注意這邊不是真的指「開頭」，而是第二個位數，只是因為我們現在忽略了前面的數字 2）有 2! = 2 種排列。而 2 < 3，所以不會是開頭 1、
開頭 3 加上前面的開頭總計又 2 × 2! = 4 種排列。而 4 ≧ 3，所以我們的目標排列第二個位數是 3。
因此現在問題變成「現在有 1 和 4 兩個數字，其第 1 個排列為何」。
開頭 1 有 1! = 1 種排列。而 1 ≧ 1，所以目標排列第三位數為 1。
而最後只剩一個數字「4」，因此我們便可以得到目標排列第四位數為 4。因此最後便可以知道答案為 2314。
而上述過程對於其他 n 、 k 之值也是類似的。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
