solution.md

# 全排列

<p>给定一个<strong> 没有重复</strong> 数字的序列，返回其所有可能的全排列。</p><p><strong>示例:</strong></p><pre><strong>输入:</strong> [1,2,3]<strong><br />输出:</strong>[  [1,2,3],  [1,3,2],  [2,1,3],  [2,3,1],  [3,1,2],  [3,2,1]]</pre>
<p>以下<font color="red">错误</font>的选项是？</p>

## aop

### before

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

```cpp

int main()
{
    Solution sol;
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> res;

    res = sol.permute(nums);

    for (auto i : res)
    {
        for (auto j : i)
            cout << j << " ";
        cout << endl;
    }
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<vector<int>> ans;
        vector<int> tem1, tem2;
        if (!nums.size())
            return ans;
        tem1.push_back(nums[0]);
        ans.push_back(tem1);
        for (int i = 1; i < nums.size(); i++)
        {
            int len = ans.size();
            while (len)
            {
                tem1 = ans[--len];
                ans.erase(ans.begin() + len);
                int j = i;
                while (j--)
                {
                    tem2 = tem1;
                    tem2.insert(tem2.begin() + j, nums[i]);
                    ans.push_back(tem2);
                }
            }
        }
        return ans;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<vector<int>> res;
        vector<bool> used(nums.size());
        dfs(nums, used, res);
        return res;
    }

private:
    vector<int> stack;
    void dfs(vector<int> &nums, vector<bool> &used, vector<vector<int>> &res)
    {
        if (stack.size() == nums.size())
        {
            res.push_back(stack);
        }
        else
        {
            for (int i = 0; i < nums.size(); i++)
            {
                if (!used[i])
                {
                    used[i] = true;
                    stack.push_back(nums[i]);
                    dfs(nums, used, res);
                    stack.pop_back();
                    used[i] = false;
                }
            }
        }
    }
};
```

### B

```cpp
class Solution
{
public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<vector<int>> res;

        BT(res, nums, 0);
        return res;
    }
    void BT(vector<vector<int>> &res, vector<int> &nums, int start)
    {

        if (start == nums.size())
        {
            res.push_back(nums);
            return;
        }
        else
        {
            for (int i = start; i < nums.size(); i++)
            {
                swap(nums[i], nums[start]);
                BT(res, nums, start + 1);
                swap(nums[i], nums[start]);
            }
        }
    }
};
```

### C

```cpp
class Solution
{
public:
    vector<vector<int>> result;
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<int> temp(nums.size());
        permutation(nums.size(), 0, nums, temp);
        return result;
    }
    void permutation(int n, int index, vector<int> &nums, vector<int> &temp)
    {
        if (index == n)
        {
            result.push_back(temp);
            return;
        }
        for (int i = 0; i < n; i++)
        {
            bool flag = true;
            for (int j = 0; j <= index - 1; j++)
            {
                if (temp[j] == nums[i])
                    flag = false;
            }
            if (flag)
            {
                temp[index] = nums[i];
                permutation(n, index + 1, nums, temp);
            }
        }
    }
};
```