Find all subsets withing given range

Revision en1, by Scofield11, 2019-04-22 22:33:56

For a given array $a_i$ , we need to find all subsets withing given range [A,B].

For an array consisting of $a_1$ and $a_2$ all subsets are: {},{$a_1$},{$a_2$},{$a_1$,$a_2$}.

Their sums are 0, $a_1$, $a_2$, $a_1$+$a_2$.

Input:

3 -1 2
1 -2 3


Output:

5


The 5 subsets that fit between -1 and 2 are : {} , {$a_1$},{$a_1$,$a_2$},{$a_1$,$a_2$,$a_3$},{$a_2$,$a_3$}.

I did the math and I think I got the task, I got how to solve it, I just don't know how to implement it.

My way is calculating the sum of all elements, and then reducing each element at a time to produce more subsets, and from those subsets to produce even more (unique of course) subsets, all while checking if each subset is within range of given [A,B], but I don't know how to implement it, I've never done this type of a task before. My way would have time complexity of O(2^n) and constraints on this program are 1<n<=34, -2e7 <= $a_i$ <= 2e7, -5e8 <= $a_i$ <= 5e8, would this even pass theoretically ?

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 Scofield11 2019-04-22 22:33:56 1061 Initial revision (published)