farhin_khaled

Sum of all subsets

Sep 15th, 2021
830
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define ull unsigned long long int
  4. #define pb push_back
  5. #define mp make_pair
  6. #define in insert
  7. #define f first
  8. #define sc second
  9. #define M 1000000
  10. using namespace std;
  11.  
  12. vector <int> subsetSums;
  13.  
  14. void subsetSum(int a[],int lb,int ub,int len)
  15. {
  16.   if(ub==len) return;
  17.   int sum1 = 0,sum2 = 0;
  18.   if(lb!=(ub-1) && lb!=ub) sum2 = a[lb]+a[ub];
  19.   for(int i=lb;i<=ub;i++) sum1 += a[i];
  20.   if(subsetSums.size()==0) subsetSums.pb(0);
  21.   if(subsetSums.size()<pow(2,len) && sum2) subsetSums.pb(sum2);
  22.   if(subsetSums.size()<pow(2,len)) subsetSums.pb(sum1);
  23.   subsetSum(a,lb,ub+1,len);
  24.   subsetSum(a,lb+1,lb+1,len);
  25. }
  26.  
  27. int main()
  28. {
  29.   int a[] = {1,2,3};
  30.   int sz = sizeof(a)/sizeof(a[0]);
  31.   subsetSum(a,0,0,sz);
  32.   for(auto i: subsetSums) cout << i << " ";
  33.  
  34.   return 0;
  35. }
RAW Paste Data