Advertisement
shabbyheart

Sum of sub set algorithm

Nov 16th, 2019
253
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 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. //            for(int i=1;i<=k;i++)
  13. //            {
  14. //                cout<<x[i]<<" ";
  15. //            }
  16. //                cout<<endl;
  17.         }
  18.  
  19.         else if (s+w[k]+w[k+1]<=m)
  20.             sum(s+w[k],k+1,r-w[k]);
  21.  
  22.         if((((s+r)-w[k])>=m) &&(s+w[k+1])<=m)
  23.         {
  24.             x[k] = 0;
  25.             sum(s,k+1,r-w[k]);
  26.         }
  27.     }
  28.     void display(int k)
  29.     {
  30.         for(int i=1;i<=k;i++)
  31.         {
  32.             if( x[i] == 1)
  33.                 cout<<w[i]<<" ";
  34.         }
  35.         cout<<endl;
  36.     }
  37. };
  38. int main()
  39. {
  40.     freopen("input.txt","r",stdin);
  41.     SumofsubSet ss;
  42.     cin>>n>>m;
  43.     int total = 0;
  44.     for(int i =1; i<=n;i++)
  45.     {
  46.         cin>>w[i];
  47.         total = total+ w[i];
  48.     }
  49.     ss.sum(0,1,total);
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement