A variant of subset sum problem

general
,
1

I was trying to solve this problem on some other site, but couldnt find an optimal algo which meets its constraints. Here it goes -

There exists an array A consisting of N numbers. Output the number of subsets of the array A whose sum is greater than or equal to K.
1 <= N <= 40
1 <= A[i], K <= 10^16

Had K been smaller, I could have used a dp approach with complexity O(nk) to count all such subsets. But I wonder how does one solve this problem with such big constraint on K?

2

Hey this can be done using meet in the middle technique.

What we actually do is divide the array into two small arrays.
let’s say N=40,then we take first 20 elements in our first array and remaining 20 elements in another array.Now we find all possible subset sums for both arrays using recursion which has time complexity of (2^20).store all possible subset sums of first array in one vector(say v1) and 2nd array in another vector (say v2).
sort both the vectors and traverse the first vector and find lower bound for k-v1[i] in second vector and add that index to your answer.Hope this helps and comment if you have any doubt.

Time complexity of this is O(klog(k)) where k=2^20.

Here is an another similar question https://www.codechef.com/MAY17/problems/CHEFCODE
and my solution is here https://www.codechef.com/viewsolution/13455499

3 Likes
3

i think this is what you are looking for https://www.quora.com/What-are-the-good-ways-to-solve-a-subset-sum-problem

Look for Raziman T.V’s Solution where he explains the case N > 2^|S1|.

1 Like
4

Thanks and specially for the codechef problem for me to practice on

1 Like