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?