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
innovolt:
20140326 18:44:17
start from brute force and then small optimization,not too tough as it seems... 

paras meena:
20140215 20:19:28
I think weak Test cases =P 

Rishav Goyal:
20140205 22:20:23
really enjoyed !! while solving it !! 

aqfaridi:
20140124 19:03:47
nice.. 

Sumit Kumar:
20130829 20:37:39
Can the numbers in the sequence repeat? 

super human:
20130820 17:14:32
awesome problem....learnt something new..!!! 

$!:D:
20130524 14:33:46
Last edit: 20130603 12:19:31 

Tejas Joshi:
20130316 22:36:27
Really nice problem !! 

:
20130304 00:31:07
Nice Problem ! 

:D:
20090831 08:59:15
There are 2^N subsets for a given set and ALL are counted as distinct. 
Added by:  Neal Wu 
Date:  20090119 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 