题目描述

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。

我们假设对于小写字母有 a<b<…<y<z，而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入格式

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

输出格式

输出这个字符串的所有排列方式，每行一个排列。

要求字母序比较小的排列在前面。

字母序如下定义：

已知 S=s1s2…sk,T=t1t2…tk，则 S<T 等价于，存在 p(1≤p≤k)，使得 s1=t1,s2=t2,…,sp−1=tp−1,sp<tp 成立。

数据范围

字符串的长度在 1 到 6 之间

样例

输入样例：

abc
输出样例：

abc
acb
bac
bca
cab
cba

算法1

DFS

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define N 16

char a[N];      // 输入的字符串
bool st[N];     // 标记字符是否被使用
char res[N];    // 保存当前排列
int len;        // 字符串长度

void dfs(int n) {
    if (n == len) { // 当当前排列长度等于字符串长度时，输出结果
        res[n] = '\0'; // 添加字符串结尾
        printf("%s\n", res);
        return;
    }

    for (int i = 0; i < len; i++) { // 遍历每个字符
        if (!st[i]) { // 如果当前字符未被使用
            st[i] = true;       // 标记为已使用
            res[n] = a[i];      // 将字符加入当前排列
            dfs(n + 1);         // 递归处理下一个位置
            st[i] = false;      // 回溯，标记为未使用
        }
    }
}

int main() {
    scanf("%s", a);    // 输入字符串
    len = strlen(a);   // 获取字符串长度
    dfs(0);            // 从位置 0 开始递归
    return 0;
}