SUBSUMS  Subset Sums
Given a sequence of N (1 ≤ N ≤ 34) numbers S_{1}, ..., S_{N} (20,000,000 ≤ S_{i} ≤ 20,000,000), determine how many subsets of S (including the empty one) have a sum between A and B (500,000,000 ≤ A ≤ B ≤ 500,000,000), inclusive.
Input
The first line of standard input contains the three integers N, A, and B. The following N lines contain S_{1} through S_{N}, in order.
Output
Print a single integer to standard output representing the number of subsets satisfying the above property. Note that the answer may overflow a 32bit integer.
Example
Input: 3 1 2 1 2 3 Output: 5
The following 5 subsets have a sum between 1 and 2:
 0 = 0 (the empty subset)
 1 = 1
 1 + (2) = 1
 2 + 3 = 1
 1 + (2) + 3 = 2
hide comments
matias222:
20200824 06:21:29
Finally after 1 week of trying AC, it is a meet in the middle problem, just focus on doing a right bs


goa_baba:
20200616 21:04:11
very poor test cases!


bhati_r45:
20200516 07:27:20
the first 14 test cases are very weak and finally got ac


scolar_fuad:
20191220 07:43:44
my first meet in the middle dp ... bitmask + binary search ...


shadow13325:
20190912 04:54:26
can anyone help me with the binary search approach?? 

kshubham02:
20190725 20:01:33
Hint : Thinking process is similar to problem  ABCDEF. 

great_coder1:
20190705 11:06:32
My first meet in the middle problem


hetp111:
20190529 16:42:04
If, array is 1 2 2 1, then 1+2 and 2+1 is counted twice in the sub set sum array, but still the solution got accepted.. how? Are all the elements distinct in input ? Last edit: 20190529 16:43:20 

hetp111:
20190529 15:51:06
Binary Search + Bitmasking 

purohit:
20190403 07:03:54
TLE using recurison 
Added by:  Neal Wu 
Date:  20090119 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 