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.
The first line of standard input contains the three integers N, A, and B. The following N lines contain S1 through SN, in order.
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.
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
all the heroes in comment who are posting did one attempt or writing very basic question like that are fools , dont listen to them and try on your own , but this question is really hard and the approach used to actually solve the question needs to you to already know about subsets and subsequences and how to calculate them and more so dont worry and look it up on utube.
I have a doubt.
Earlier got a WA on test case 15, just needed to use long long int for the output variable (which stores the number of subsets).
Prerequisites: Meet in the meet algo. Don't waste much time come back after learning the aforementioned algo.Last edit: 2021-09-03 09:03:47
those who are finding difficulty in this, don't worry it is actually hard question
very basic and straight forward problem just meet in middle and binary search.
Use long long int and fast i/p & o/p
Use long long int.