The is practice problem MARCHA1 from code chef

payingUp.cpp

#include <iostream>

using namespace std;
// for each subset calculate the sum and compare with expected sum
bool checkSetBitAndValidateSum(long *array, long b, long sum) {
   long i=0;
   long runningSum=0;

   while (b>0) {
      if(b&1) { // check if bit is set
         // if bit is set find the corresponding element from array 
        // add the element to running sum
         runningSum += array[i];    

      }
      i++;
      b = b>>1; 
   }      
   return (runningSum != 0) && (runningSum == sum);    
}

// find all subsets of array
bool findSubsetEqualToSum(long* array, long n, long sum){
   
   long i=1, range=(1<<n)-1;        
   for(;i<=range;i++){
     	if(checkSetBitAndValidateSum(array,i,sum)) {
        return true;
     	}
   }
   return false;
}


bool process() {
   long n,sum;
   cin>>n>>sum;   
   long array[n];
   for(long i=0;i<n;i++){
     cin>>array[i];
   } 	    
   return findSubsetEqualToSum(array,n,sum);
	
}

int main() {

   int t;
   cin>>t;
   bool result[t];
   for(int i=0;i<t;i++){
   	result[i]=process();
   }
   for(int i=0;i<t;i++){
      if(result[i]) {
        cout<<"Yes\n";
      } else {
        cout<<"No\n";
      }
  }
}