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
bluejam:
20170622 11:02:01
Empty subset should either be considered or not considered in the final value.


coolio_1:
20170621 15:33:03
Nice problem!! Take care whether the empty subset sum lies in the range [a,b] or not.


up79:
20170619 17:36:09
ac finally :)


sas1905:
20170605 10:10:20
recursive dp using maps gives TLE..!! 

akash619j:
20170602 10:16:56
can anyone explain return value of lower_bound and upper_bound...i m bit confused with it..though i am getting correct answer on subtracting them!! 

quantic:
20170524 17:07:27
conceptual problem! 

rraj001:
20170520 11:16:02
good concept!!worth the time :) 

ashishranjan28:
20170514 11:05:14
nice :) 

Omar:
20160810 00:07:17
Meet in the middle approach , plus bit masking to generate subsets , i liked it . 

square1001:
20160726 06:57:55
Yeah, today I've solved 3 meetinthemiddle algorithm problems.

Added by:  Neal Wu 
Date:  20090119 
Time limit:  0.328s0.657s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 