程序员面试题精选100题(59)-字符串的组合[算法]

题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。

分析：在本系列博客的第28题《字符串的排列》中，我们详细讨论了如何用递归的思路求字符串的排列。同样，本题也可以用递归的思路来求字符串的组合。

假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；而是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码：

void Combination(char* string){if(string == NULL)return;int length = strlen(string);vector<char> result;for(int i = 1; i <= length; ++ i){Combination(string, i, result);}}void Combination(char* string, int number, vector<char>& result){if(number == 0){vector<char>::iterator iter = result.begin();for(; iter < result.end(); ++ iter)printf("%c", *iter);printf("\n");return;}if(*string == '\0')return;result.push_back(*string);Combination(string + 1, number - 1, result);result.pop_back();Combination(string + 1, number, result);}

由于组合可以是1个字符的组合，2个字符的字符……一直到n个字符的组合，因此在函数void Combination(char* string)，我们需要一个for循环。另外，我们一个vector来存放选择放进组合里的字符。

博主何海涛对本博客文章享有著作权。网络转载请注明出处http://zhedahht./。整理出版物请和作者联系。对解题思路有任何建议，欢迎在评论中告知，或者加我微博/zhedahht或者/zhedahht与我讨论。谢谢。