Scofield11's blog

Find all subsets withing given range
By Scofield11, history, 6 years ago, In English

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 ?

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

The statement you've given is a bit confusing. I am presuming you mean you want all subsets with sum in the range [A, B].

Your idea seems to be to use bruteforce to generate all subsets, which are $$$2^n$$$ as you've correctly found. This can be implemented quite concisely using recursion. Feel free to ask if you can't seem to figure out a nice way to implement it.

The problem, however, is not intended to be solved like this. Usually $$$O(2^n)$$$ solutions have the constraint $$$n<=20$$$ or at most $$$n<=25$$$, but for $$$n=34$$$ the solution is most likely not that.

The real solution, however, is not that different. It's a technique called "meet in the middle". You can look it up or you can ask for more details about it, but if you struggle implementing the regular bruteforce, perhaps you should focus more on the basics.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain more about how to solve it use this using "meet in the middle"? Also, can you explain "meet in the middle" or any useful links and questions?

    → Reply
»
6 years ago, # |
  Vote: I like it -17 Vote: I do not like it

$$$O(NB/64)$$$ possible with bitset. Should pass if the TL is 3 seconds: 

bitset<B> bs; bs[0] = 1; 
for(int i = 1; i <= n; ++i) {
  if(a[i] >= 0) bs |= bs << a[i]; 
  else bs |= bs >> (-a[i]); 
}
// bs[i] = 1 means there is a subset with sum i

^ this assumes $$$A, B$$$ both are positive. If you want to handle negative numbers too, then you need to offset the indexes. That is number $$$i$$$ goes to position $$$i + offset$$$, and becomes positive.

→ Reply