程式員面試題精選-- 字元串的組合

  分類： 程式員面試題 2011-10-07 15:05   5人閱讀   評論(0)   收藏   舉報

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

用遞歸的思路來求字元串的組合:

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

參考代碼：

view plain

1. #include<iostream>  
2. #include<vector>  
3. using namespace std;  
4. void Combination(char *str, unsigned int number, vector<char> &result);   
5. void Combination(char *str)  
6. {  
7.     if(!str)  
8.         return;  
9.     unsigned int length = strlen(str);  
10.     vector<char> result;  
11.     for(int i=1; i<=length; i++)  
12.     {//依次求 i 個字元組成的序列   
13.         Combination(str, i, result);  
14.     }  
15. }   
16. void Combination(char *str, unsigned int number, vector<char> &result)  
17. {  
18.     if(number == 0)  
19.     {// i 個字元的某個序列已選取完，輸出之   
20.         vector<char>::iterator index = result.begin();  
21.         for(; index < result.end(); index++)  
22.         {  
23.             cout<<*index;  
24.         }  
25.         cout<<endl;  
26.         return;  
27.     }  
28.     if(*str == '\0')  
29.         return;  
30.     //把目前字元放入序列中，在剩下的串中選取number-1個字元的序列   
31.     result.push_back(*str);  
32.     Combination(str+1, number-1, result);  
33.     result.pop_back();  
34.     //不把目前字元放入序列中，在剩下的串中選取number個字元的序列  
35.     Combination(str+1, number, result);  
36. }  
37. int main()  
38. {  
39.     char *str = "abcd";  
40.     Combination(str);  
41.     system("pause");  
42.     return 0;  
43. }