1、全排列简介

比如对于一个序列：[1,2,3]、这个序列的全排列就是：

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
全排列的定义十分简单。我们在刷题的过程中也经常会碰见一些需要求全排列的题目。比如：链接字符串的排列、链接把数组排成最小的数等。接下来我们用递归的思路去实现下数的全排列。

2、递归思路

比如对于序列[1,2,3]。其全排列过程其实是这样的：我们首先固定住1，然后对2、3进行全排列。在对2、3进行全排列的过程中呢，我们采取的方法也是一样的，就是固定住2，对3进行全排列。（由此可以看出这里可以用递归）固定住1的全排列排完之后呢，我们就要开始固定2的全排列了。直至固定完每一位数实现全部的排列组合。

3、代码实现

void perm(int pos, vector<int> &num, vector<vector<int>> &all_result) {
    if (pos + 1 == num.size()) {
        // 一次全排列的结果
        all_result.push_back(num);
        return;
    }
    for (int i = pos; i < num.size(); ++i) {
        swap(num[pos], num[i]); //先固定一个值
        perm(pos+1, num, all_result); //对剩下的进行全排列
        swap(num[pos], num[i]); //要恢复序列的原始序列
    }
}
int main() {
    vector<int> num = {1, 2, 3};
    vector<vector<int>> all_result; //存放全排列结果的容器
    perm(0, num, all_result);
}

4、算法复杂度

时间复杂度：O(N*N!),全排列的时间复杂度为N！，每次排列结果需要遍历一次nums数组。
空间复杂度：O（1）。

5、STL中的全排列

以上是我们自己写的全排列，但是STL中也给我们提供了全排列函数：std::next_permutation(first, last)。例子：

#include <algorithm>
#include <string>
#include <iostream>

int main()
{
    std::string s = "aba";
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << '\n';
    } while(std::next_permutation(s.begin(), s.end()));
}
/*
output:
aab
aba
baa
*/

5、运用场景

我们只要根本题目本身加上相应的逻辑即可。（比如上面两道全排列题目）