给定一个按大下排列好的数列,如A[8]={1,2,3,4,5,8,10,12}; 任意给定一个整数N(比如N=14),求出和为N的所有子集。
思路:递归求解,化解为小问题;用栈保存所有和为N的各个项。
#include<iostream> #include<stack> using namespace std;
int A[8]={1,2,3,4,5,8,10,12}; stack<int> S; void makeSum(int index,int sum){ for(int i=index;i>=0;i--){ S.push(A[i]);//当前元素入栈 int remainder=sum-A[i];//计算下一个元素 if(remainder==0){//满足条件,输出栈中的所有元素 stack<int> temp=S; while(!temp.empty()){ cout<<temp.top()<<" "; temp.pop(); } cout<<endl; S.pop();//出栈 continue; } if(i==0){//计算到末尾,返回 S.pop(); return; } int j=0; if(A[j]>remainder){ S.pop(); continue; } while(j<=i-1){ // 找到不大于remainder的第一个数,可改进为 二分查找 if(A[j]>=remainder) break; j++; } if(A[j]>remainder || j>i-1) j--; makeSum(j,remainder);//递归求解 S.pop(); } } void main(){ makeSum(7,14); }
注意到,每次递归中,都要遍历所有元素,其实是没必要的,
比如,在第一层递归中,sum=14,就没必要遍历 i=4,3,2,1的元素,因为,其和不可能等于14,所以我们可以用一个辅助数组保存前N项和,在遍历时判断是否还需要继续遍历
需要花费O(n)的空间;
改动后如下所示:
int A[8]={1,2,3,4,5,8,10,12}; int Sum[8]={0}; stack<int> S; void makeSum(int index,int sum){ for(int i=index;i>=0 && sum<=Sum[i];i--){ S.push(A[i]);//当前元素入栈 int remainder=sum-A[i];//计算下一个元素 if(remainder==0){//满足条件,输出栈中的所有元素 stack<int> temp=S; while(!temp.empty()){ cout<<temp.top()<<" "; temp.pop(); } cout<<endl; S.pop();//出栈 continue; } if(i==0){//计算到末尾,返回 S.pop(); return; } int j=0; if(A[j]>remainder){ S.pop(); continue; } while(j<=i-1){ // 可改进为 二分查找 if(A[j]>=remainder) break; j++; } if(A[j]>remainder || j>i-1) j--; makeSum(j,remainder);//递归求解 S.pop(); } } void main(){ Sum[0]=A[0];// Sum 用来计算前n项和,减少没必要的计算,但需要花费O(n)的空间 for(int i=1;i<8;i++){ Sum[i]=A[i]+Sum[i-1]; } makeSum(7,14); }
=================2013-6-20============================
再看自己的算法,发现上述过程还是麻烦,没有领悟递归的真正写法,应力求简单明了
//下面算法中的index 与上述两个算法中的index 表示意思不同,上面的表示索引下标。
int A[8]={1,2,3,4,5,8,10,12}; int Sum[8]={0}; stack<int> S; //index 表示元素个数 //sum 表示要求的和 void makeSum(int index,int sum){ if(sum==0){//满足条件,输出栈中的所有元素 stack<int> temp=S; while(!temp.empty()){ cout<<temp.top()<<" "; temp.pop(); } cout<<endl; return; } for(int i=index-1;i>=0 && sum<=Sum[i];i--){ if(A[i]<=sum){ S.push(A[i]);//当前元素入栈 makeSum(i,sum-A[i]); S.pop(); } } } void main(){ Sum[0]=A[0];// Sum 用来计算前n项和,减少没必要的计算,但需要花费O(n)的空间 for(int i=1;i<8;i++){ Sum[i]=A[i]+Sum[i-1]; } makeSum(8,14); }