【ACWing】3429. 全排列

题目地址：

https://www.acwing.com/problem/content/description/3432/

给定一个由不同的小写字母组成的字符串$s$，输出这个字符串的所有全排列。我们假设对于小写字母有$a<b<\dots <y<z$，而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入格式：
输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在$1$到$6$之间。

输出格式：
输出这个字符串的所有排列方式，每行一个排列。
要求字母序比较小的排列在前面。
字母序如下定义：已知$S=s_1{s}_2\dots s_k,T=t_1{t}_2\dots t_k$，则$S<T$等价于，存在$p(1\le p\le k)$，使得 $s_1=t_1,s_2=t_2,\dots ,s_{p-1}=t_{p-1},s_p<t_p$成立。

数据范围：
字符串的长度在$1$到$6$之间。

可以DFS，依次枚举当前位置填哪个字母，每一层从小到大枚举所有字母。代码如下：

#include 
using namespace std;

bool vis[7];
string s, t;

void dfs(int u) {
  if (u == s.size()) cout << t << endl;
  for (int i = 0; i < s.size(); i++) {
    if (vis[i]) continue;
    t[u] = s[i];
    vis[i] = true;
    dfs(u + 1);
    vis[i] = false;
  }
}

int main() {
  cin >> s;
  t.resize(s.size());
  dfs(0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度$O(n!)$，$n$为$s$长度，空间$O(n)$。