字符串求幂集

昨天晚上看了下字符串的一些小程序，自己试写了程序，不做题目还真会大脑会退化，很早以前的题目。居然不会。。 问题的分析很重要，没有分析好算法，就直接写程序，怎么写都不正确。看来以后拿到题目好好分析个可行的模型才敢动键盘，否则一进去就回不来啊。
幂集构造二个思路
1.假设字符串是ABC，从空集开始构造，从左向右构造，到字母A时，有两条路可以走，要A然后往前走，不要A然后往前走。一直取完字符串为止。
回溯： str:原字符串， cur当前走到的字符串， i当前走到第几步， len字符总长度 PowerSet(char* str, char* cur,int i, int len) { char* strTmp = (char*)malloc(sizeof(char)*len); if(i>=len) //走到了最后一步 { printf("{%s}",str); return; } else { //不要第i+1个字符往前走 strncpy(strTmp,str,i); PowerSet(str, strTmp,i+1,len);
//要了第i+1个字符串 strncpy(strTmp,str,i+1); PowerSet(str,strTmp,i+1,len); } }
第二个思路就是把空集看成是一个二叉树的根节点，左子树不取字符，右子树取字符。这样所有的叶子节点就是一个幂集。具体的代码用二叉树的遍历，就是输出条件是深度为len.