用c语言dfs输出前N个大写字母的有重复全排列

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

void dfs(int n, int len, char* str, int* vis) {
if (len == n) {
printf("%s\n", str);
return;
}
for (int i = 0; i < n; i++) {
if (!vis[i]) {
str[len] = 'A' + i;
vis[i] = 1;
dfs(n, len + 1, str, vis);
vis[i] = 0;
}
}
}

int main() {
int n;
printf("请输入N：");
scanf("%d", &n);
char* str = (char*)malloc(sizeof(char) * (n + 1));
str[n] = '\0';
int* vis = (int*)malloc(sizeof(int) * n);
memset(vis, 0, sizeof(int) * n);
dfs(n, 0, str, vis);
free(str);
free(vis);
return 0;
}

相关问题

用C语言输出前N个字母的有重复全排列 Input 输入一个数值N 1<=N<=10 Output 输出前N个大写字母的有重复全排列 Sample Input 2 Sample Output AA AB BA BB

要输出前N个大写字母的有重复全排列，可以使用递归的方式来实现。首先，定义一个数组来存储字母，然后编写一个递归函数来生成全排列。

以下是用C语言实现的代码示例：

#include <stdio.h>

void generatePermutations(char* letters, int n, char* prefix, int index) {
    // 递归终止条件：当生成的排列长度达到n时，输出排列并返回
    if (index == n) {
        printf("%s\n", prefix);
        return;
    }

    // 递归生成排列
    for (int i = 0; i < n; i++) {
        prefix[index] = letters[i];
        generatePermutations(letters, n, prefix, index + 1);
    }
}

void printDuplicatePermutations(int n) {
    // 定义大写字母数组
    char letters[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    // 定义前缀数组，用于存储生成的排列
    char prefix[n + 1];
    prefix[n] = '\0';  // 添加字符串结束符

    // 生成全排列
    generatePermutations(letters, n, prefix, 0);
}

int main() {
    int N;
    printf("请输入一个数值N：");
    scanf("%d", &N);

    if (N < 1 || N > 10) {
        printf("输入的N超出范围！");
        return 0;
    }

    printf("前%d个大写字母的有重复全排列如下：\n", N);
    printDuplicatePermutations(N);

    return 0;
}

运行示例：

请输入一个数值N：2
前2个大写字母的有重复全排列如下：
AA
AB
BA
BB

用c语言dfs输出n个数的有重复全排列

下面是使用C语言实现DFS输出n个数的有重复全排列的示例代码：

#include <stdio.h>

#define MAXN 10

int n;
int a[MAXN];
int vis[MAXN];

void dfs(int step)
{
    if (step == n) {
        for (int i = 0; i < n; ++i) {
            printf("%d ", a[i]);
        }
        printf("\n");
        return;
    }

    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            vis[i] = 1;
            a[step] = i;
            dfs(step + 1);
            vis[i] = 0;
        }
    }
}

int main()
{
    scanf("%d", &n);
    dfs(0);
    return 0;
}

在这个示例代码中，我们使用了一个数组a来存储当前的排列，使用vis数组来记录哪些数字已经被使用过了。在dfs函数中，我们先判断是否已经完成了一次排列，如果完成了，就直接输出结果并返回；否则就从1到n枚举当前位置可以放置的数字，如果这个数字还没有被使用过，就将其放入数组a中，并标记vis数组中对应的位置为已使用，然后递归调用dfs函数继续生成下一个位置的数字，最后将vis数组中对应位置的标记撤销，以便后续的排列可以使用这个数字。

需要注意的是，这个示例代码中并没有去重，也就是说，如果n个数字中有重复的数字，那么会生成重复的排列。如果需要去重，可以在dfs函数中添加一个判断，如果当前位置可以放置的数字和上一个位置放置的数字相同，就直接跳过。