Advertisement
newb_ie

check subset sum exist or not using bitset

Jul 8th, 2020
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.61 KB | None | 0 0
  1. /*
  2.      ___T_    
  3.     | - + |    
  4.     |__v__|    
  5.    .=[::+]=.  
  6.  ]=' [___] '=[ => HI :-)
  7.      /  |      
  8.     _\  |_
  9.  */
  10. #include<bits/stdc++.h>
  11. using namespace std;
  12. using lli = int64_t;
  13. const int maxN = 1000;//sum of elements
  14. int main(){
  15.     ios::sync_with_stdio(false);
  16.     cin.tie(nullptr);
  17.     //check if subset sum exist or not using bitset
  18.     int n,sum;
  19.     bitset<maxN> bit;
  20.     bit[0] = 1; //we can make sum = 0 without any eleemnts;
  21.     cin >> n >> sum;
  22.     for(int i = 0;i < n; i++){
  23.         int in;
  24.         cin >> in;
  25.         bit |= (bit << in);
  26.     }
  27.     if(bit[sum]){
  28.         cout << "YES";
  29.     }else{
  30.         cout << "NO";
  31.     }
  32. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement