字符串排列组合2

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

  思路：同样是用递归求解。可以考虑求长度为n的字符串中m个字符的组合，设为C(n,m)。原问题的解即为C(n, 1), C(n, 2),...C(n, n)的总和。对于求C(n, m)，从第一个字符开始扫描，每个字符有两种情况，要么被选中，要么不被选中，如果被选中，递归求解C(n-1, m-1)。如果未被选中，递归求解C(n-1, m)。不管哪种方式，n的值都会减少，递归的终止条件n=0或m=0。

 

  代码实现如下：

 

 1 //函数功能 ： 从一个字符串中选m个元素 2 //函数参数 ： pStr为字符串， m为选的元素个数， result为选中的 3 //返回值 ：   无 4 void Combination_m(char *pStr, int m, vector<char> &result) 5 { 6     if(pStr == NULL || (*pStr == '\0'&& m != 0)) 7         return; 8     if(m == 0) //递归终止条件 9     {10         for(unsigned i = 0; i < result.size(); i++)11             cout<<result[i];12         cout<<endl;13         return;14     }15     //选择这个元素16     result.push_back(*pStr);17     Combination_m(pStr + 1, m - 1, result);18     result.pop_back();19     //不选择这个元素20     Combination_m(pStr + 1, m, result);21 }22 //函数功能 ： 求一个字符串的组合23 //函数参数 ： pStr为字符串24 //返回值 ：   无25 void Combination(char *pStr)26 {27     if(pStr == NULL || *pStr == '\0')28         return;29     int number = strlen(pStr);30     for(int i = 1; i <= number; i++)31     {32         vector<char> result;33         Combination_m(pStr, i, result);34     }35  }