Count subsets of array which qualify min(subset)+max(subset) < k

The interviewer implied that sorting the array would help and it does help. I'll try to explain.

Taking the array and k values you stated:

a = [4,2,5,7]
k = 8

Sorting the array will yield:

a_sort = [2,4,5,7]

Now we can consider the following procedure:

1. set ii = 0, jj = 1

2. choose a_sort[ii] as a part of your subset

   2.1. If 2 * a_sort[ii] >= k, you are done. else, the subset [a_sort[ii]] holds the condition and is a part of the solution.

3. add a_sort[ii+jj] to your subset

   3.1. If a_sort[ii] + a_sort[ii+jj] < k,

   3.1.1. the subset [a_sort[ii], a_sort[ii+jj]] holds the condition and is a part of the solution, as well as any subset which consists of any additional number of elements a_sort[kk] where ii< kk < ii+jj

   3.1.2. set jj += 1 and go back to step 3.

   3.2. else, set ii += 1, jj = ii + 1, go back to step 2

With your input this procedure should return:

[[2], [2,4],[2,5],[2,4,5]]
# [2,7] results in 9 > 8 and therefore you move to [4]
# Note that for [4] subset you get 8 = 8 which is not smaller than 8, we are done

Explenation

• if you have a subset of [a_sort[ii]] which does not hold 2 * a_sort[ii] < k, adding additional numbers to the subset will only yield min(subset)+max(subset) > 2 * a_sort[ii] > k and therefore there will not be any additional subsets which hold the wanted condition. Moreover, by setting a subset of [a_sort[ii+1]] will results in 2 * a_sort[ii+1] >= 2 * a_sort[ii] > k` sinse a_sort is sorted. Therefore you will not find any additional subsets.
• for jj > ii, if a_sort[ii] + a_sort[ii+jj] < k then you can push any number if members from a_sort into the subset, as long as the index kk will be bigger than ii and lower than ii+jj since a_sort is sorted, and adding these members to the subset will not change the value of min(subset)+max(subset) which will remain a_sort[ii] + a_sort[ii+jj] and we already know that this value is smaller thank k

Getting the count

In case you simply want to the possible subsets, this can be done easier than generating the subsets themselves.

Assuming that for ii > jj the condition holds, i.e. a_sort[ii] + a_sort[ii+jj] < k. If jj = ii + 1 there is an addition of 1 possible subset. If jj > ii + 1 there are jj - ii - 1 additional elements which can be either present not not without a change of the value a_sort[ii] + a_sort[ii+jj]. Therefore there are a total of 2**(jj-ii-1) additional subsets available to add to the solution group (jj-ii-1 elements, each is independently present or not). This also holds for jj = ii + 1 since in this case 2**(jj-ii-1) = 2**0 = 1

Looking at the example above:

• [2] adds 1 count
• [2,4] adds 1 count (1 = 0 + 1)
• [2,5] adds 2 counts (2 = 0 + 2 --> 2 **(2 - 0 - 1) = 2**1 = 2)

A total count of 4

1. Sort the array
2. For an element x at index l, do a binary search on the array to get index of the maximum integer in the array which is < k-x. Let the index be r.
3. For all subsets where min(subset) = x, we can have any element with index in range (l,r]. Number of subsets with min(subset) = x becomes the total number of possible subsets for (r-l) elements, so count = 2^(r-l) (or 0 if r<l).
   (Note: in all such subsets, we are fixing x. That's why the range (l,r] isn't inclusive of l)
4. You have to iterate over the array, use the above process for each element/index to get the count of subsets where our current element is the minimum and the subset satisfies the given constraint. If you find an element with count=0, break the iteration.

This should work with a 0(N*log(N)) complexity, good enough for an interview question imo.

For the given example, sorted array = [2,4,5,7].

1. For element 2, l=0 and r=2. Count = 2^(2-0) = 4 (covers [2],[4,2],[2,5],[4,2,5]
2. For element 4, l=1 and r=0. Count = 0, and we break the iteration.