品才網>面試>程序員面試題100題-字符串的組合[算法]

程序員面試題100題-字符串的組合[算法]

時間：2022-07-13 16:14:54 面試我要投稿

相關推薦

程序員面試題精選100題-字符串的組合[算法]

題目：輸入一個字符串，輸出該字符串中字符的所有組合。舉個例子，如果輸入abc，它的組合有a、b、c、ab、ac、bc、abc。

程序員面試題精選100題-字符串的組合[算法]

分析：在本系列博客的第28題《字符串的排列》中，我們詳細討論了如何用遞歸的思路求字符串的排列。同樣，本題也可以用遞歸的思路來求字符串的組合。

假設我們想在長度為n的字符串中求m個字符的組合。我們先從頭掃描字符串的第一個字符。針對第一個字符，我們有兩種選擇：一是把這個字符放到組合中去，接下來我們需要在剩下的n-1個字符中選取m-1個字符;而是不把這個字符放到組合中去，接下來我們需要在剩下的n-1個字符中選擇m個字符。這兩種選擇都很容易用遞歸實現。下面是這種思路的參考代碼：

void Combination(char* string)

{

if(string == NULL)

return;

int length = strlen(string);

vectorresult;

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

{

Combination(string, i, result);

}

void Combination(char* string, int number, vector& result)

{

if(number == 0)

{

vector::iterator iter = result.begin();

for(; iter < result.end(); ++ iter)

printf("%c", *iter);

printf(" ");

return;

}

if(*string ==