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 ?

Tags #c++, subset, #array

History

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