C语言递归实现带重复的全排列问题。例如:输入{1,3,1}; 输出:{1,3,1},{1,1,3},{3,1,1}。
时间: 2024-12-10 07:52:56 浏览: 10
在C语言中,递归是一种强大的工具,可以用来解决像全排列这类需要多次调用自身的问题。对于带重复元素的全排列,我们需要考虑避免重复的组合。这里是一个简单的递归函数实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义数组和长度
#define SIZE 3
int arr[SIZE] = {1, 3, 1};
// 用于存储当前结果的临时数组
int temp[SIZE];
void permute(int start) {
if (start == SIZE) {
// 如果已经遍历到数组末尾,就打印出结果
for (int i = 0; i < SIZE; ++i)
printf("%d", temp[i]);
printf("\n");
return;
}
// 遍历所有剩余元素
for (int i = start; i < SIZE; ++i) {
// 将当前元素复制到临时数组
temp[start] = arr[i];
// 递归地处理剩下的元素
permute(start + 1);
// 回溯,移除已放置的元素
arr[i] = arr[start]; // 如果不回溯,会生成重复组合
}
}
int main() {
permute(0);
return 0;
}
```
这个程序首先检查是否到达了数组末尾,如果到了则打印结果。然后在每个递归步骤中,它选择一个元素并将其放入结果位置,接着继续处理剩余元素。关键在于每次递归返回前,都需要将原来的位置还原回去,以免重复排列。
阅读全文