C语言实现：输入字符串的全部组合

来自剑指offer上相关题目拓展，居然磨了我两天的功夫，我可能学的是假的编程。

代码是用纯C写的，题目要求是将输入字符串的所有组合全部输出，例如输入a,b,c三个字符，则它们的组合有a, b, c, ab, ac, bc, abc.

当交换两个字符时，虽然排列顺序变动，但还是算作一个组合，即ab和ba算作同一个，如何不重复的输出这些组合呢？

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 25

void combination_op(char* pstr, char* output, int m);
void combination(char* pstr);


int main(){
//	char* pstr = "";
	char pstr[MAX] = "";
//	FILE *fp = fopen("input.txt", "r");

	printf("输入待处理的字符串:n");
	while(gets(pstr) != NULL);

	combination(pstr);

/*	if(fp != NULL){
		while(fgets(pstr, sizeof(pstr), fp) != NULL);
		combination(pstr);
	}
*/
	return EXIT_SUCCESS;
}

void combination(char* pstr){
	int cap;

	if(pstr == NULL){
		printf("空串！n");
		return;
	}
	for(cap = 1; cap <= (int)strlen(pstr); cap++){
		char output[MAX] = "";
		combination_op(pstr, output, cap);
	}
}
void combination_op(char* pstr, char* output, int m){
	/*
	**当剩下的字符恰好够组合时，直接全部复制到输出字串中。
	*/
	if((int)strlen(pstr) == m){
		strcat(output, pstr);
		printf("%sn",output);
		*(output + (int)strlen(output) - m - 1) = '';//回溯
		return;
	}
	/*
	**输出串已满时
	*/
	if(m <= 0){
		printf("%sn", output);	
		*(output + (int)strlen(output) - 1) = '';//回溯
	}else{
		//添加当前字符
		strncat(output, pstr,1);
		combination_op(pstr+1, output, m-1);
		//不添加当前字符
		combination_op(pstr+1, output, m);
	}
}

把输入的n个字符看成两部分：第一个字符和其余所有的字符。

如果组合中包含第一个字符，则下一步在剩余的n-1个字符里选取m-1个字符；

如果组合不包含第一个字符，则下一步在剩余的n-1个字符里选取m个字符。

借着这个思路用递归来写，思路不难，但实现起来遇到不少困难，具体代码也注释过了。

另外一种思路:

实际上这道题也可以用二进制数来控制输出，大概就是用一个位数等于输入字符串长度的二进制数来控制。

是否包含对应位置上的字符，从0......0001依次递增到1......1111对应0位置上的字符不显示，这样就实现了对组合的控制。

时间复杂度O(n),如果用位数组实现的话空间复杂度也会到达O(n)，考虑到字符串长度有限，不妨用unsigned或者long long会节省下来空间。

不知道我有时间会不会去尝试一下呢。

下面放上运行结果：

首先是输入单个字符和多个字符的情况：

考虑鲁棒性输入空串和空指针：

至此结束，一面试题能为难我这么久也是服了自己了，希望能顺利通过研考吧！

最后

以上就是柔弱战斗机为你收集整理的C语言实现：输入字符串的全部组合的全部内容，希望文章能够帮你解决C语言实现：输入字符串的全部组合所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。