SUBSUMS - Subset Sums


Given a sequence of N (1 ≤ N ≤ 34) numbers S1, ..., SN (-20,000,000 ≤ Si ≤ 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 S1 through SN, 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 32-bit 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: 2020-08-24 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: 2020-06-16 21:04:11

very poor test cases!
does it considers only distinct subsets?
for eg if arr->(1,2,2)
does it consider -> {},{1},{2},{1,2},{1,2,2},{2,2}
or -> {},{1},{2},{2},{1,2},{1,2},{2,2},{1,2,2}?
I was considering the later case & getting wrong answer on the last test case

bhati_r45: 2020-05-16 07:27:20

the first 14 test cases are very weak and finally got ac

scolar_fuad: 2019-12-20 07:43:44

my first meet in the middle dp ... bitmask + binary search ...
happy coding

shadow13325: 2019-09-12 04:54:26

can anyone help me with the binary search approach??

kshubham02: 2019-07-25 20:01:33

Hint : Thinking process is similar to problem - ABCDEF.

great_coder1: 2019-07-05 11:06:32

My first meet in the middle problem

hetp111: 2019-05-29 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: 2019-05-29 16:43:20
hetp111: 2019-05-29 15:51:06

Binary Search + Bitmasking

purohit: 2019-04-03 07:03:54

TLE using recurison


Added by:Neal Wu
Date:2009-01-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO