# 【LeetCode】 60. 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.

> Note:
> - Given n will be between 1 and 9 inclusive.
> - Given k will be between 1 and n! inclusive.

> 一個集合[1,2,3,...,n]，它總共擁有n!種不同的排列組合。
> 以下照順序列出了n=3的時候的所有組合：
> 1. "123"
> 2. "132"
> 3. "213"
> 4. "231"
> 5. "312"
> 6. "321"

> 給予n和k，請回傳第k種排列。

> 提示：
> - n將會介於1到9之間(包含)。
> - k將會介於1到n!之間(包含)。

## Example:

Example 1:

Input: n = 3, k = 3
Output: "213"


Example 2:

Input: n = 4, k = 9
Output: "2314"

## Solution

* 因為我這類的題目很弱，直接使用了`algorithm`函式庫裡面的`next_permutation`。
* 缺點是速度很慢，因為理論上可以直接一步求得結果，但用這個方法你必須用Loop去跑k種組合。

### Code

class Solution {
public:
    string getPermutation(int n, int k) {
        string ans(n,0);
        for(int i=0;i<n;i++)
            ans[i]='1'+i;
        for(int i=0;i<k-1;i++)
            next_permutation(ans.begin(),ans.end());
        return ans;
    }
};

###### tags: `LeetCode` `C++`