版权声明：本文为博主原创文章，未经博主同意不得转载。
https://blog.csdn.net/mmc_maodun/article/details/26405471
转载请注明出处：http://blog.csdn.net/ns_code/article/details/26405471
剑指offer上的拓展题目，输入一个字符串。输出该字符串的字符的全部组合，比方输入字符串：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。
博主是刚開始尝试用递归去写，写了一个多小时都没写出来，桑心啊！
除了操作二叉树写递归比較顺。其它好多地方用递归愣是憋不出来。尤其字符串操作。
在何海涛博客下看到有人留言。给了个思路。认为非常不错，自己把代码写了出来。详细思路例如以下：
开辟一个于字符串相应长度的int数组（char数组也能够，并且更节省空间），用该数组模拟二进制的加1操作，则该数组的元素仅仅能为0或1，我们规定假设该数组某个位置处的元素是1。则字符串相应位置处的字符參与组合，假设为0，则字符串相应位置处的字符不參与组合。这样讲该int数组。从全0加到全1，便可得到字符串的全部组合。
这里没有去除反复子串，也没依照字典序输出，假设要求依照字典序输出，并去掉反复子串的话。能够採取上道题目一样的办法。先将全部的字符串保存在字符串数组中，而后通过快排使数组中的字符串依照字典序排列。再在输出的时候，跳过反复的字符串。
实现代码例如以下：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
/*
模拟二进制加1操作，当最高位要进位时，说明全部的位都是1，返回false。
用char数组来模拟比int数组更省空间。这里必须传入数组长度len，
因为我们CominationAll中将要传入的字符数组全部初始化为了'\0',
假设在该函数内部用strlen计算的话，会得到len=0。
*/
bool Increment(char *BindAdd,int len)
{
if(BindAdd == NULL)
return false;
BindAdd[len-1]++;
int i;
for(i=len-1;i>=0;i--)
{
if(BindAdd[i] >= 2)
{
if(i == 0)
{
BindAdd[i]--;
return false;
}
else
{
BindAdd[i] -= 2;
BindAdd[i-1]++;
}
}
else
break;
}
return true;
}
/*
输出字符串的全部组合
*/
void CominationAll(char *str)
{
if(str == NULL)
return;
int len = strlen(str);
char *BindAdd = (char *)malloc(len*sizeof(char));
if(BindAdd == NULL)
exit(EXIT_FAILURE);
memset(BindAdd,0,len*sizeof(char));
while(Increment(BindAdd,len))
{
int i;
for(i=0;i<len;i++)
{
if(BindAdd[i] == 1)
putchar(str[i]);
}
putchar('\n');
}
free(BindAdd);
BindAdd = NULL;
}
int main()
{
char str[10];
while(gets(str))
CominationAll(str);
return 0;
}測试结果：