/************************************************************************/

/* 面試題：請編寫一個函數(shù)，把字符串中的所有字符子串的各種組合形式全部都顯示出來。

  字符子串的長度范圍是從一個字符到字符串的長度。

  不管排列順序如何，只要兩種組合中的字符完全一樣，它們就是同一種組合。

  比如：給定字符串"hart"，則"ha"和"har"是不同的組合，而"ha"和"ah"是相同的組合。

  排列方式：不以字符串多少為排列區(qū)分，而是以是否確定某一字符來確定字符子串

  以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 ，就成了新的組合。

  根據(jù)這樣的特點：我們設(shè)計一個遞歸算法

  （1）從首字符到尾字符的各個字符，循環(huán)

  （2）輸出被循環(huán)到的字符

  （3）如果循環(huán)的字符 后面還有字符，遞歸；以后面的字符為起點，重復(fù)步驟（2）和步驟（3）

  （4）如果被循環(huán)到的字符后面沒有字符，跳出循環(huán)。

  畫圖的話，看成如下：以行為單位輸出，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";  //此法當有重復(fù)字母時，結(jié)果是錯誤的

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;

}