我在之前的一篇文章中，写的是关于全排列问题的小结(http://www.cnblogs.com/wangkundentisy/p/8570082.html)，这篇文章主要介绍的为字符串的组合问题。首先需要弄清楚排列和组合的区别，对于字符串"abc"，它的全排列包括：abc、acb、bac、bca、cab、cba。但它的所有组合为：a、b、c、ab、ac、bc、abc。也就是说一个长度为n的字符串，它的组合包括长度为1~n的所有字符子串(忽略顺序)。下面具体探讨一下字符串的组合问题的实现。
在求长度为n的字符串的组合时，我们要遍历从1到n所有的子串，当求长度为m(1≤m≤n)的组合时，可以把那个字符分成两部分：第一个字符和其余所有的字符。此时就分为两种情况了：
(1)组合包含第一个字符，则下一步在剩余字符里选取m-1个字符。
(2)组合不包含第一个字符，则下一步在剩余的n-1个字符中选取m个字符。
很明显，这个用递归实现比较清晰。总的来说，可以把求n个字符组成对的长度为m的组合问题分成两个子问题，即分别求n-1个字符中长度为m-1的组合；以及求n-1个字符中长度为m的组合。
代码如下：
#include<iostream>
#include<cassert>
#include<vector>
#include<stack>
#include<unordered_map>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
void CombinationCore(char * str, int len, vector<char> &rs)
{
if(len == 0)//相当于此时的组合串的长度满足最开始的要求了,即m==0
{
vector<char>::iterator it;
for(it = rs.begin(); it < rs.end(); it++)
cout<<(*it);
cout<<endl;
return;
}
if(*str == ' ')//即n == 0
return;
rs.push_back(*str);
//把当前字符当做组合的一部分
CombinationCore(str + 1,len - 1,rs);
rs.pop_back();//删除当前字符，恢复之前的状态
//不把当前字符作为组合的一部分
CombinationCore(str + 1, len,rs);
}
void getCombination(char* str)
{
if(str == nullptr)
return;
int length = strlen(str);
vector<char> rs;
for(int i = 1; i <= length; i++)
CombinationCore(str,i,rs);
}
int main()
{
char s[] = "abcd";
getCombination(s);
}
结果如下：
此处有几点需要注意的：
1.len表示组合串的长度，即m。
2.注意递归的终止条件：*str == ' '和len == 0，对于前者相当于已经遍历完整个字符串了，此时直接返回即可；对于后者，相当于找到符合的组合串，所以要处理结果(可以打印或存储，本例是打印)，然后返回执行寻找下一种长度的组合串。
3.由于要考虑两种情况，先考虑第一种情况，把当前字符算入组合串中，然后需要从rs中删除当前字符串(即恢复原状)，才考虑第二种情况。