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