/************************************************************************/
/* 面试题:请编写一个函数,把字符串中的所有字符子串的各种组合形式全部都显示出来。
字符子串的长度范围是从一个字符到字符串的长度。
不管排列顺序如何,只要两种组合中的字符完全一样,它们就是同一种组合。
比如:给定字符串"hart",则"ha"和"har"是不同的组合,而"ha"和"ah"是相同的组合。
排列方式:不以字符串多少为排列区分,而是以是否确定某一字符来确定字符子串
以hart作为字符串,则如下:
h ha har hart hat hr hrt ht
a ar art at
r rt
t
可以看出:第一行全有h,第二行没有h,全是art,第三行没有ha,全是rt,第四行没有har,就只有t
且 如果第一行去掉 h,恰好是 第二行 第三行 第四行 的全部,正好是 后3个字符art的组合,
再黏上一个 h ,就成了新的组合。
根据这样的特点:我们设计一个递归算法
(1)从首字符到尾字符的各个字符,循环
(2)输出被循环到的字符
(3)如果循环的字符 后面还有字符,递归;以后面的字符为起点,重复步骤(2)和步骤(3)
(4)如果被循环到的字符后面没有字符,跳出循环。
画图的话,看成如下:以行为单位输出,1表示此字符输出
h a r t h a r t
h 1 . . . h 1 . . .
a 1 1 . . --》 a 1 1 . .
r 1 1 1 . r 1 1 . 1 //下一行返回后,本行往下一列进行,后面的依次类推
t 1 1 1 1(return) t 1 1 1 1
*/
/************************************************************************/
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
int length;
char *out;
char str[]="hart"; //此法当有重复字母时,结果是错误的
int sum=0;
void DoCombine(char in[],char out[],int length,int rec,int start)//rec看成行,
{
int i;
for( i = start; i < length; i++)//i看成列
{
out[rec] = in[i];
out[rec+1] =0;
printf("%s\n",out);
if(i< length-1)
DoCombine(in,out,length,rec+1,i+1);
}
}
int main(int argc, char* argv[])
{
length = strlen(str);
out = (char *)malloc(length +1);
DoCombine(str,out,length,0,0);
getchar();
return 0;
}
联系客服