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 }