Number of Subsets problem

general
, ,
1

Given an array of n numbers, we have to find the number of subsets with sum >= a number, k

Constraints:-
N<=40
Ai,K<=10^16

Problem LINK

2

Split the array into 2 arrays of equal size. Find all the subsets of each array, and sort them. For each possible subset of the left array, binary search to find the number of subsets that are greater than k.

1 Like
3

What about the cases when some part of a subset is from left array and some part from the right half. How will you be counting those?

4

You misinterpreted. The subsets of the full array can be represented as pairs of subsets from each half. Now for each element in the left half, you want to find the number of elements in the right half that give a sum a greater than k.