输入一个字符串，输出该字符串中字符的所有组合。例如输入abc，它的组合有a、b、c、ab、ac、bc、abc。在前面学习全排列算法时，讲到了如何用递归的思路求字符串的排列。同样，本题也可以用递归的思路来求字符串的组合。假设在长度为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>::const_iterator iterBegin = result.begin();
vector<char>::const_iterator iterEnd = result.end();

for (; iterBegin != iterEnd; ++ iterBegin)
printf(“%c”, *iterBegin);

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来存放选择放进组合里的字符。

注：本文在转载时，稍做修改，不影响作者原意。在作者给出的参考代码中，没有考虑重复字符的问题。另外本题的解法还有一些比较好的思路，比如：“用一个数组，模拟2进制加法器，某一位为1，则取对应的字符，若为0则不取，就能够实现字符组合。”。或者与之相似的另一种思路：“设有n个字符。int num 从 1 自增到 2^n -1, 将num右移i位，跟1做按位&操作，即可判断第i个字符取还是不取。”，关于这种思路的参考代码如下：

void Combination(char *string)
{
if (string == NULL)
return;

int length = strlen(string);
int num = pow(2.0, length) ;

for (int i = 1; i < num; ++i)
{
for(int j = 0; j < length; ++j)
{
if ((i >> j) & 1)
printf(“%c”, string[j]);
}
printf(“\n”);
}

}