求字元串的所有組合輸出

劍指Offer一書中面試題28求字元串的排列，給出了遞歸算法程式。其中擴充題目中提到了，求字元串的所有組合。比如輸入字元串：“abc”，輸出應為：a、b、c、ab、ac、bc、abc.

借用書上的解題思路：如果輸入n個字元，則這n個字元能構成長度為1、長度為2、......長度為n的組合。在求長度為m的組合時，可考慮将這n個字元分成兩部分：第一個字元和其餘所有的字元。如果組合裡包含第一個字元，則下一步在剩餘的字元裡選取m-1個字元；如果不包含第一個字元，則下一步在剩餘的字元裡選取m個字元。

思想比較簡單巧妙，下面是我給出的實作代碼：

#include "stdafx.h"

#include <iostream>

#include <string>

using namespace std;

void Combine(int ilen,char* pStart,char* PEnd,string strBefore)

{

if (ilen<0||pStart+ilen-1>PEnd)

{

return;

}

else

{

if (pStart+ilen-1==PEnd)

{

if (!strBefore.empty())

{

cout<<strBefore;

}

printf("%s\n",pStart);

}

else

{

if (ilen==0)

{

if (!strBefore.empty())

{

cout<<strBefore;

cout<<endl;

}

}

else

{

Combine(ilen,pStart+1,PEnd,strBefore);//不包含第一個字母

strBefore.push_back(*pStart);

Combine(ilen-1,pStart+1,PEnd,strBefore);

}

}

}

}

void Combine(char* pStr,int ilen)

{

if (pStr==NULL||ilen<1)

{

return;

}

char* pEnd=pStr+ilen-1;

string strb;

for (int i=1;i<=ilen;i++)

{

if (!strb.empty())

{

strb.clear();

}

Combine(i,pStr,pEnd,strb);

}

}

int _tmain(int argc, _TCHAR* argv[])

{

char* str="abcd";

Combine(str,4);

return 0;

}

運作結果如圖：