Advertisement
shabbyheart

Sum of sub set algorithm

Nov 17th, 2019
286
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int w[100000],x[100000],m,n;
  4. class SumofsubSet{
  5. public:
  6.     void sum(int s,int k,int r)
  7.     {
  8.         x[k] = 1;
  9.         if(s+w[k] == m)
  10.         {
  11.             display(k);
  12.         }
  13.  
  14.         else if (s+w[k]+w[k+1]<=m)
  15.             sum(s+w[k],k+1,r-w[k]);
  16.  
  17.         if((((s+r)-w[k])>=m) &&(s+w[k+1])<=m)
  18.         {
  19.             x[k] = 0;
  20.             sum(s,k+1,r-w[k]);
  21.         }
  22.     }
  23.     void display(int k)
  24.     {
  25.         for(int i=1;i<=k;i++)
  26.         {
  27.             if( x[i] == 1)
  28.                 cout<<w[i]<<" ";
  29.         }
  30.         cout<<endl;
  31.     }
  32. };
  33. int main()
  34. {
  35.     ifstream fin("input.txt", ios::in) ;
  36.     //freopen("input.txt","r",stdin);
  37.     SumofsubSet ss;
  38.     fin>>n>>m;
  39.     int total = 0;
  40.     for(int i =1; i<=n;i++)
  41.     {
  42.         fin>>w[i];
  43.         total = total+ w[i];
  44.     }
  45.  
  46. //    outfile.open("input.txt");
  47. //     outfile.close();
  48. fin.close();
  49.     int a,b,c;
  50.     cin>>a>>b;
  51.     cout<<a<<b;
  52.     ss.sum(0,1,total);
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement