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
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.


rajeshranjan:
20160207 09:26:01
great question,good concept building of #bitmask and binary search combo... 

manas0008:
20160206 19:16:31
Try to use divide and conquer approach(minimises time & space).....learnt bitmasking.......STL helped a lot!!............It has made my day. Last edit: 20160206 19:20:40 

abhi_6991:
20160206 12:30:56
Bitmasking ,binary search!!! Last edit: 20160206 13:21:37 

minhthai:
20160125 11:09:41
very nice question :D 

GAURAV CHANDEL:
20151229 19:25:26
Cool ... very cool.... 

aghori_sadhu:
20151020 20:22:33
A great question....indeed bitmask + binary search :D 

karan:
20150619 16:04:53
nice problem :) 

Aman:
20150529 19:27:43
Last edit: 20150529 19:29:11 
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 JS 