（1）方法一，背包问题解法
1 #include <iostream> 2 using namespace std; 3 #include <vector> 4 #include <list> 5 6 //采用背包问题方法，从后向前，最后一个放和不放背包里，注意递归退出条件和sum==n后，没有return而是继续 7 vector<int> a; //存背包 事实证明用vector就可以，也不用revers。 8 9 void subofsum(int sum,int n,bool &flag) 10 { 11 if(sum<=0||n<=0) //迭代退出条件 12 return; 13 if(sum==n) 14 { 15 16 for(vector<int>::iterator i=a.begin();i!=a.end();i++) 17 { 18 cout<<*i<<"+"; 19 flag=true; 20 } 21 cout<<n<<endl; //注意n没有放入背包，而是输出了，而且后面没有return，让n接着放入背包，肯定不行，就会弹出北包，放subofsum（sum，n-1，flag）； 22 23 } 24 a.push_back(n); 25 subofsum(sum-n,n-1,flag); 26 a.pop_back(); 27 subofsum(sum,n-1,flag); 28 } 29 30 int main() 31 { 32 int sum=13; 33 int n=9; 34 bool flag=false; 35 subofsum(sum,n,flag); 36 if(flag==false) 37 { 38 cout<<"not found"<<endl; 39 } 40 system("PAUSE"); 41 }
方法二：子集和问题方法，其实跟背包问题差不多。
自己实现的，原来看懂跟自己能写对差距好大啊，自己写就费了很大劲。真的要练习才行，光看是没用的，只能眼高手地。
问题：思路很简单，回溯方法，加上修建树枝。
我做的是t ，k ，当t+k==m,
t+k<m,t+k+1<=m&&t+r-k>=m
常规还可以用vector直接放每一个数字，而不是用类似bitmap方法，那种也可以直接用下面的改写，但是空间占用比较多。
1 #include <cstdlib> 2 #include <iostream> 3 #include <string.h> //memset must include string.h or ctring 4 using namespace std; 5 6 /* 7 * 8 */ 9 void subofsum(int t,int k,int r,bool *array,int n,bool &flag,int sum) 10 { 11 // if(k>n) //这里开始担心k会越界，实际上不会，因为有剪支12 // return; 13 //array[k]=true; 14 if(t+k==sum) //注意k没有至位 15 { 16 for(int i=1;i<=n;i++) //注意这里是n，july写的是k，想得周到，但这是常规方法 17 { 18 if(array[i]==true) 19 { 20 cout<<i<<"+"; 21 } 22 } 23 cout<<k<<endl; //cout k 24 flag=true;
return; //可以返回了 25 } 26 //array[k]=false; //这里往下有两种情况，都是针对t+k《m的情况，t+k如果大于m直接就跳过两个if了，也就是上面return了，一样。 27 if(t+k<sum) //只有当t+k《sum时才至位，上来就一直小于一直至位，知道发现不行了或等于了，推出上一层，看另外情况 28 { 29 array[k]=true; //k set 1 30 subofsum(t+k,k+1,r-k,array,n,flag,sum); 31 array[k]=false; //k not set 1 ;normal 在把k恢复，这是常规方法
if(t+k+1<=sum&&t+r-k>=sum) //另一种情况 35 { 37 subofsum(t,k+1,r-k,array,n,flag,sum); 38 }
} 34 39 } 40 41 int main(int argc, char** argv) { 42 43 int sum=13; 44 int n=9; 45 cout<<"sum= "<<"n= "<<endl; 46 cin>>sum>>n; 47 if(n<=0||sum<=0) //这里只有当n《=0时，说明错了，sum可以比n小，也可以比n大，但是sum不能是负数 48 return 1; 49 bool * array=new bool[n+1]; 50 //bool array[10]={0}; 51 memset(array,0,sizeof(bool)*(n+1)); 52 bool flag=false; 53 int r=n*(n+1)/2; 54 subofsum(0,1,r,array,n,flag,sum); 55 if(!flag) 56 cout<<"nof found"<<endl; 57 return 0; 58 }
july博客方法实现
1 void subofsum(int t,int k,int r,bool *array,int n,bool &flag,int sum) 2 { 3 // if(k>n) //because have cut ,so k won't > n,k not set 1 4 // return; 5 array[k]=true; //注意上来就至位了 6 if(t+k==sum) 7 { 8 for(int i=1;i<=k;i++) //这是关键，只是到k，因为上来就至位，又没有恢复，就会导致后面可能还有1，所以他只用到k，很巧妙，但不常见 9 { 10 if(array[i]==true) 11 { 12 cout<<i<<""; //最后会多输出一个空格 13 } 14 } 15 cout<<endl; 16 flag=true; 17 return; 18 } 19 else //else可以不用写，上面return了，就算不return也可以不用写else，因为如果上面成立，下面都不会成立 20 { 21 if(t+k+k+1<=sum) //多看个k+1 22 { 23 subofsum(t+k,k+1,r-k,array,n,flag,sum); 24 } 25 if(t+k+1<=sum&&t+r-k>=sum) 26 { 27 array[k]=false; 28 subofsum(t,k+1,r-k,array,n,flag,sum); 29 } 30 } 31 }
总结：一定要自己动手实习，这样才能真正弄明白自己，可能之前一直没注意到的细节，不能眼高手地啊！