Morass

repair

Jun 19th, 2016
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.14 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define sf scanf
  6. #define pf printf
  7.  
  8.  
  9. vector<int> ara;
  10. vector<int> result;
  11. vector<int> res2[1000];
  12. bool mark[15],flag;
  13. int sum,total,n,INDEX;
  14.  
  15.     void call(int t)
  16.     {
  17.         if(sum==total)
  18.         {
  19.             res2[INDEX++]=result;
  20.             flag=true;
  21.             return;
  22.  
  23.         }
  24.  
  25.         else if(sum>total) return;
  26.  
  27.         for(int i=t;i<n;i++)
  28.         {
  29.             result.push_back(ara[i]);
  30.             sum+=ara[i];
  31.             call(i+1);
  32.             result.pop_back();
  33.             sum-=ara[i];
  34.         }
  35.  
  36.  
  37.     }
  38.  
  39.     bool cmp (vector<int>a,vector<int>b)
  40.     {
  41.         for(int i=0;i<a.size();i++)
  42.         {
  43.             if(a[i]==b[i]) continue;
  44.             return a[i]>b[i];
  45.         }
  46.  
  47.         return a.size()>b.size();
  48.     }
  49.  
  50. int main()
  51. {
  52.     int i,x;
  53.  
  54.     while(sf("%d",&total))
  55.     {
  56.         sf("%d",&n);
  57.         if(total==0&&n==0) break;
  58.         //cout<<n<<endl;
  59.         for(i=0;i<n;i++)
  60.         {
  61.             sf("%d",&x);
  62.             ara.push_back(x);
  63.         }
  64.  
  65.         //memset(mark,0,sizeof(mark));
  66.  
  67.         result.clear();
  68.         flag=false;
  69.         sum=0;
  70.         INDEX=0;call(0);
  71.         pf("Sums of %d:\n",total);
  72.         if(!flag) pf("NONE\n");
  73.  
  74.         else
  75.         {
  76.             sort(res2,res2+INDEX,cmp);
  77.  
  78.             for(int j=0;j<res2[0].size();j++)
  79.             {
  80.  
  81.                     if(j==0)pf("%d",res2[0][j]);
  82.                     else
  83.                     {
  84.                         pf("+%d",res2[0][j]);
  85.                     }
  86.             }
  87.             pf("\n");
  88.  
  89.             for(i=1;i<INDEX;i++)
  90.             {
  91.                 if(res2[i-1]==res2[i])
  92.                     continue;
  93.  
  94.                 for(int j=0;j<res2[i].size();j++)
  95.                 {
  96.                     if(j==0)pf("%d",res2[i][j]);
  97.                     else
  98.                     {
  99.                         pf("+%d",res2[i][j]);
  100.                     }
  101.                 }
  102.                 pf("\n");
  103.             }
  104.         }
  105.  
  106.         for(i=0;i<INDEX;i++) res2[i].clear();
  107.  
  108.         ara.clear();
  109.     }
  110.  
  111.  
  112.     return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment