solution.md

# 排列序列

<p>给出集合 <code>[1,2,3,...,n]</code>，其所有元素共有 <code>n!</code> 种排列。</p><p>按大小顺序列出所有排列情况，并一一标记，当 <code>n = 3</code> 时, 所有排列如下：</p><ol>	<li><code>"123"</code></li>	<li><code>"132"</code></li>	<li><code>"213"</code></li>	<li><code>"231"</code></li>	<li><code>"312"</code></li>	<li><code>"321"</code></li></ol><p>给定 <code>n</code> 和 <code>k</code>，返回第 <code>k</code> 个排列。</p><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>n = 3, k = 3<strong><br />输出：</strong>"213"</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>n = 4, k = 9<strong><br />输出：</strong>"2314"</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>n = 3, k = 1<strong><br />输出：</strong>"123"</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>1 <= n <= 9</code></li>	<li><code>1 <= k <= n!</code></li></ul>
<p>以下<font color="red">错误</font>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    int n = 3;
    int k = 3;
    string res;

    res = sol.getPermutation(n, k);
    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    string getPermutation(int n, int k)
    {
        string res;
        vector<int> candidates;

        vector<int> factorial(n + 1);
        factorial[0] = 1;
        int fact = 1;
        for (int i = 1; i <= n; i++)
        {
            candidates.push_back(i);
            fact *= i;
            factorial[i] = fact;
        }
        k -= 1;
        for (int i = n - 1; i >= 0; i--)
        {
            int index = k / factorial[i];
            k = index * factorial[i];
            res.push_back(candidates[index] + '0');
            candidates.erase(candidates.begin() + index);
        }
        return res;
    }
};
```
## 选项


### A

```cpp

class Solution
{
public:
    vector<string> res;
    string getPermutation(int n, int k)
    {
        string track;
        traverse(track, n);
        return res[k - 1];
    }
    void traverse(string &track, int n)
    {

        if (track.size() == n)
        {
            res.push_back(track);
            return;
        }
        for (int i = 1; i <= n; i++)
        {
            char c = i + '0';
            if (find(track.begin(), track.end(), c) != track.end())
                continue;

            track.push_back(c);
            traverse(track, n);
            track.pop_back();
        }
    }
};
```

### B

```cpp
class Solution
{
public:
    string getPermutation(int n, int k)
    {
        string ans;

        vector<bool> st(n + 1);

        for (int i = 1; i <= n; i++)
        {

            int f = 1;

            for (int j = n - i; j >= 1; j--)
                f *= j;

            for (int j = 1; j <= n; j++)
            {

                if (!st[j])
                {

                    if (k <= f)
                    {
                        ans += to_string(j);
                        st[j] = 1;
                        break;
                    }

                    k -= f;
                }
            }
        }
        return ans;
    }
};
```

### C

```cpp
class Solution
{
public:
    int th;
    string ans;
    string getPermutation(int n, int k)
    {
        string s;
        vector<bool> vec(9, false);
        this->th = 0;

        backtrack(n, k, s, vec);

        return ans;
    }

    bool backtrack(int n, int k, string &s, vector<bool> &vec)
    {

        if (s.length() == n)
        {
            if (++th == k)
            {
                ans = s;
                return true;
            }
        }

        for (char c = '1'; c <= '1' + n - 1; c++)
        {

            if (vec[c - '1'])
                continue;

            s.push_back(c);
            vec[c - '1'] = true;

            if (backtrack(n, k, s, vec))
                return true;

            s.pop_back();
            vec[c - '1'] = false;
        }
        return false;
    }
};
```