題目描述 輸入一個集合，需要生成該集合所能得出的所有組合。舉例說明：若輸入集合為{1,2} ， 需要生成的組合有{1}，{1, 2}，{2} 。該題目與生成集合的全排列有很多相似之處，同樣也是一個很經典的問題。 解決思路 這裡我們利用遞歸的思想來實現該問題的解。 面對這樣一個問題，我們需要仔細分析。題目要求生成一個集合的所有組合，也就是需要生成集合裡的元素所能夠組成的所有組合。於是一個很明顯的思路就是要遍歷該集合。一提到遍歷集合，可以使用循環或者遞歸來實現。針對本問題，利用遞歸的思想是很方便的。 假設我們的集合為{1，2，3} ，我們從頭掃描集合的元素，第一個元素為1。對於這個元素，我們可以把他放到組合集中，然後在剩下的集合裡再去選擇；也可以不把他放到組合集中，在剩下的集合裡去選擇元素放到組合集中。一般化的，假設我們的集合有n個元素，要求m個元素的組合。我們掃描每一個元素，針對該元素，我們可以將其放到組合集中，然後在剩下的n-1個元素中再選擇m-1個元素；我們也可以不放該元素進集合，而直接從剩下的n-1個元素中選擇m個元素。這已經是非常清晰的遞歸的思想了，具體代碼如下。 代碼 [cpp] void combination(char *src,int num, vector<char>& result) { if(num==0) { vector<char>::iterator iter=result.begin(); for(;iter<result.end();iter++) { printf("%c",*iter); } printf("\n"); return; } if(*src=='\0') return; result.push_back(*src); combination(src+1,num-1,result); result.pop_back(); combination(src+1,num,result); } void all_sub_set(char *src) { assert(src); if(!src) return; int i=0; int len=strlen(src); vector<char> result; for(i=1;i<=len;i++) { combination(src,i,result); } } 小結 遞歸生成集合的所有組合，是考驗一個程序員編程基本功的問題，有一些技巧性。本問題與Gray Code按序生成集合子集屬於同一個問題的不同實現方法，都是很經典的解題方法。
