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.
InputThe first line of standard input contains the three integers N, A, and B. The following N lines contain S1 through SN , in order.
OutputPrint 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.
Input:
3 -1 2
1
-2
3Output:
5The 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
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.