用c语言dfs输出n个数的有重复全排列
时间: 2024-01-29 08:04:00 浏览: 30
下面是使用C语言实现DFS输出n个数的有重复全排列的示例代码:
```c
#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函数中添加一个判断,如果当前位置可以放置的数字和上一个位置放置的数字相同,就直接跳过。
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)