AcWing 3429. 全排列
原题链接
简单
作者:
lemoba
,
2024-11-02 21:53:03
,
所有人可见
,
阅读 1
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
char arr[7]; // 原字符串
char path[7]; // 输出路径字符串
bool flag[7]; // 标记是否被选中到path[]中
int n; // 原字符串的长度
void dfs(int i)
{
if(i == n) // 当递归到底部时输出路径
{
cout << path << endl;
return ;
}
for(int j = 0;j < n;j ++) // 遍历原数组中剩余没有选上的字符
{
if(!flag[j])
{
path[i] = arr[j]; // 如果没有选上就进入路径
flag[j] = true; // 并被标记已经在路径中
dfs(i + 1); // 继续往深处递归
flag[j] = false; // 递归结束,开始回溯,恢复现场
// 这里没有必要将arr[j]移除path,因为i这个位置已经被标记,走另一条分支时会直接覆盖
}
}
}
int main()
{
cin >> arr;
n = strlen(arr);
dfs(0);
return 0;
}